#include <cstdio>
#include <vector>
#define NMAX 50023
#define QMAX 1000023
using namespace std;
int n,m;
bool vis[NMAX],as;
int ps=2,ct[NMAX],q[QMAX];
long long cost[NMAX];
vector<int> adj[NMAX],cst[NMAX];
void bfs(int pt)
{
     printf("%d %d\n",pt,ps);
     if(pt==ps) return;
     vis[q[pt]]=0;
     vector<int>::iterator it1,it2;
     for(it1=adj[q[pt]].begin(),it2=cst[q[pt]].begin();it1!=adj[q[pt]].end();++it1,++it2)
     {
           
       //    printf("%d %d %d\n",cost[*it1],cost[q[pt]],*it2);
           if(cost[*it1]>cost[q[pt]]+*it2)
           {
              cost[*it1]=cost[q[pt]]+*it2;
              if(vis[*it1]==0) 
              {
                               q[ps]=*it1;
                               vis[*it1]=1;
                               ++ps;
              }
              ++ct[*it1];
              if(ct[*it1]>n)
              {
                                as=1;
                                return;
              }
           }
     }
     printf("A\n");
     bfs(pt+1);
     return;
}
int main()
{
    freopen ("bellmanford.in","r",stdin);
  //  freopen ("bellmanford.out","w",stdout);
    scanf("%d%d",&n,&m);
    int a1,a2,ctt;
    for(int i=1;i<=m;i++)
    {
            scanf("%d%d%d",&a1,&a2,&ctt);
            adj[a1].push_back(a2);
            cst[a1].push_back(ctt);
    }
    for(int i=2;i<=n;i++) cost[i]=100000000000;
    cost[1]=0;
    q[1]=1;
    vis[1]=1;
    bfs(1);
    if(as==1) printf("Ciclu negativ!\n");
    else
    {
        for(int i=2;i<=n;i++) printf("%lld ",cost[i]);
    }
}