RT。蒟蒻的做法是先跑一遍 dfs 看是否能到 n，然后再用差分约束建边跑 spfa。但是最后一个 Subtask T 飞了qwq。

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5,M=2e3+5;
long long n,m,idx;
int x[M],y[M],head[N];
struct stu{
	int v,next,w;
}edge[2*M];
void add(int x,int y,int w)
{
	edge[++idx]={y,head[x],w};
	head[x]=idx;
}
int dis[N],vis[N],num[N];
bool spfa(int s)
{
	memset(dis,0x3f,sizeof(dis)),dis[s]=0;
	memset(vis,0,sizeof(vis)),vis[s]=1;
	queue<int>q;q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop(),vis[u]=0;
		for(int i=head[u];i;i=edge[i].next)
		{
			int v=edge[i].v,w=edge[i].w;
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				num[v]=num[u]+1;
				if(num[v]>=n)return false;
				if(!vis[v])vis[v]=1,q.push(v);
			}
		}
	}
	return true;
}
int need[N][N],ok[N];
void dfs(int u)
{
	if(vis[u])return;
	if(u==n){ok[u]=1;return;}
	vis[u]=1;
	for(int i=head[u];i;i=edge[i].next)
	{
		int v=edge[i].v;
		dfs(v);
		if(ok[v])need[u][v]=1,ok[u]=1;
	}
	vis[u]=0;
}
int main()
{
	srand(time(0));
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>x[i]>>y[i];
		add(x[i],y[i],1);
	}
	dfs(1);
	if(!ok[1]){cout<<-1;return 0;}
	idx=0,memset(head,0,sizeof(head));
	for(int i=1;i<=m;i++)
	{
		if(need[x[i]][y[i]])
		{
			add(x[i],y[i],9);
			add(y[i],x[i],-1);
		}
	}
	if(!spfa(1))cout<<-1;
	else{
		cout<<n<<' '<<m<<"\n";
		for(int i=1;i<=m;i++)
		{
			cout<<x[i]<<' '<<y[i]<<' ';
			if(!need[x[i]][y[i]])cout<<1+rand()%9<<"\n";
			else cout<<dis[y[i]]-dis[x[i]]<<"\n";
		}
	}
	return 0;
}