#include using namespace std; struct node{ int v,w; }; int dis[1000001];int n,m,s; int h[1000001]; vector a[1000001]; priority_queue<pair,vector<pair >,greater<pair > > q; void dij(int s){ memset(dis,0x3f,sizeof(dis)); dis[s]=0; q.push(make_pair(0,s)); while(!q.empty()){ int u=q.top().second; q.pop(); if(h[u])continue; h[u]=1; for(int i=0;idis[u]+w){ dis[v]=dis[u]+w; q.push(make_pair(dis[v],v)); } } } } int d[1000001]; queueqq; bool spfa(int u){ memset(dis,0x3f,sizeof(dis)); dis[u]=0; qq.push(u); d[u]++; while(!qq.empty()){ int u=qq.front(); qq.pop(); if(h[u])continue; h[u]=0; for(int i=0;idis[u]+w){ dis[v]=dis[u]+w; if(h[v]==0){ h[v]=1; qq.push(v); if(d[u]>=n) return 0; } } } } return 1; } int main(){

cin>>n>>m;
for(int i=1;i<=m;i++){
	int u,v,w;
	cin>>u>>v>>w;
	a[u].push_back(node{v,w});
}
for(int)
spfa(1);

return 0;

}//必定对