```c++
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+5;
const int Mod = 1e9+7;
struct node{
	int v,w;
};
int n,m,dis[N],book[N],cnt[N],f[N],g[N];
vector<node>e[N];
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		e[x].push_back({y,z});
	}
	priority_queue<pair<int,int> >q;
	memset(dis,0x3f,sizeof(dis));
	dis[1] = 0;
	q.push({0,1});
	memset(g,0x3f,sizeof(g));
	f[1] = g[1] = 0;
	cnt[1] = 1;
	while(!q.empty()){
		int tmp = q.top().second;
		q.pop();
		if(book[tmp])continue;
		book[tmp] = 1;
		for(auto T:e[tmp]){
			int v = T.v;
			int w = T.w;
			if(dis[v]>dis[tmp]+w){
				dis[v] = dis[tmp]+w;
				cnt[v] = cnt[tmp];cnt[v]%=Mod;
				g[v] = g[tmp]+1;
				f[v] = f[tmp]+1;
				q.push({-dis[v],v});
			}
			else if(dis[v]==dis[tmp]+w){
				cnt[v]+=cnt[tmp];cnt[v]%=Mod;
				g[v] = min(g[v],g[tmp]+1);
				f[v] = max(f[v],f[tmp]+1);
			//	q.push({-dis[v],v}); 
			}
		}
	}
	cout<<dis[n]<<" "<<cnt[n]<<" "<<g[n]<<" "<<f[n]<<endl;
	return 0;
}
/*
10 20
6 7 5
7 6 5
10 8 4
1 2 3
4 5 2
2 3 2
7 9 4
7 4 5
5 7 2
5 6 3
6 7 4
7 8 5
3 8 5
2 7 4
9 10 5
2 3 5
8 9 3
3 4 3
9 8 2
3 7 1

*/
```
```c++
#include <bits/stdc++.h>
/*
 * f[i][j] = f[f[i][j-1]][j-1]
 */
using namespace std;
#define int long long
const int N = 2e5+5;
int n,m,f[N][35];
vector<int>e[N];
signed main() {
    cin>>n>>m;
    for (int i=1;i<=n;i++) {
        int x;
        cin>>x;
        e[i].push_back(x);
        f[i][0] = x;
    }
    for (int j=1;j<=34;j++) {
        for (int i=1;i<=n;i++) {
            f[i][j] = f[f[i][j-1]][j-1];
        }
    }
    for (int i=1;i<=m;i++) {
        int x,y;
        cin>>x>>y;
        for (int j=34;j>=0;j--) {
            if (y>=(1LL<<j)) {
                x = f[x][j];
                y-=(1LL<<j);
            }
        }
        cout<<x<<endl;
    }
    return 0;
}
```
```c++
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+5;
int n,m,nxt[N],f[N][35],vis[N],dep[N];
void dfs(int x) {
    vis[x] = 1;
    if (!vis[nxt[x]]) {
        dfs(nxt[x]);
    }
    dep[x] = dep[nxt[x]]+1;
}
int Go(int x,int y) {
    for (int j=34;j>=0;j--) {
        if (y>=(1LL<<j)) {
            x=f[x][j];
            y-=(1LL<<j);
        }
    }
    return x;
}
signed main() {
    cin>>n>>m;
    for (int i=1;i<=n;i++) {
        cin>>nxt[i];
        f[i][0] = nxt[i];
    }
    for (int j=1;j<=34;j++) {
        for (int i=1;i<=n;i++) {
            f[i][j] = f[f[i][j-1]][j-1];
        }
    }
    for (int i=1;i<=n;i++) {
        if (!vis[i])dfs(i);
    }
    for (int i=1;i<=m;i++) {
        int x,y;
        cin>>x>>y;
        int dx=dep[x],dy=dep[y],dz=Go(x,dx);
        int res = -1;
        if (dx>=dy && Go(x,dx-dy)==y)res=dx-dy;
        else if (Go(dz,dep[dz]-dy)==y)res=dep[dz]-dy+dx;
        cout<<res<<endl;
    }
    return 0;
}
```
```c++
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int n,book[N],vis[N],pre[N],ans[N];
vector<int>e[N];
void dfs(int x)
{
	book[x] = 1;
	for(int i=0;i<e[x].size();i++){
		int v = e[x][i];
		if(vis[v]==0){
			ans[v] = ans[x]+1;
			dfs(v);
			//cout<<v<<" "<<x<<endl;
		//	cout<<ans[v]<<"   "<<ans[x]<<endl;
		}
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		e[x].push_back(i);
		pre[i] = x;
	}
	for(int i=1;i<=n;i++){
		if(!book[i]){
			int v = i;
			while(book[v]==0){
				book[v] = 1;
				v = pre[v];
			}
			int st = v;
			vector<int>circle;
			do{
				vis[st] = 1;
				circle.push_back(st);
				st = pre[st];
			}while(st!=v);
			for(auto rt:circle){
		//		cout<<rt<<endl;
				ans[rt] = circle.size();
				dfs(rt);
			}
		}
	}
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<" ";
	}
	return 0;
}
```