#includeusing namespace std;int dist[100001],head[100001],v[100001],tot,t,w,q[100001],f[10001],wer[110000],n;struct node{int next;int to;int dis;}a[30001];void add(int x,int y,int z){a[++tot].to=y;a[tot].dis=z;a[tot].next=head[x];head[x]=tot;}void spfa(){memset(dist,0x7f,sizeof(dist));memset(v,0,sizeof(v));memset(q,0,sizeof(q));t=w=0;dist[1]=0;w++;q[w]=1;while(t{t++;int k=q[t];v[k]=0;for(int i=head[k];i!=0;i=a[i].next){int jj=a[i].to;int ww=a[i].dis;if(dist[jj]>dist[k]+ww){dist[jj]=dist[k]+ww;wer[jj]=wer[k]+1;if(wer[jj]>n-1){coutreturn;}if(!v[jj]){w++;v[jj]=1;q[w]=jj;}}}}coutreturn;}int main(){int T,m;cin>>T;for(int i=1;i{cin>>n>>m;for(int i=1;i{int x,y,z;cin>>x>>y>>z;add(x,y,z);if(z>=0)add(y,x,z);}spfa();}return 0;}