#include <stdio.h>
#include <vector>
#define dmax 2000000000

using namespace std;
FILE *f=fopen("bellmanford.in","r");
FILE *g=fopen("bellmanford.out","w");

vector<int>a[50005];

int v[50005],n,m,x,y,z,use[50005],i,r,apar[50005];
int belmann(int k)
{
    int i,c[500105],p,u,ct=0,nc;
    p=1;
    u=1;
    c[p]=1;
    for(i=2;i<=n;i++)
        v[i]=dmax;
    use[1]=1;
    while(p<=u)
    {
        for(int i=0;i<a[c[p]].size();i++)
        {
            ct++;
            if (ct%2==1)nc=a[c[p]][i];else
            if (ct%2==0)
            {
                r=a[c[p]][i];
                if (v[c[p]]+r<v[nc]){
                v[nc]=v[c[p]]+r;
                if (use[nc]==0)
                {
                    u++;c[u]=nc;use[nc]=1;
                    if (apar[nc]>n)return 0;apar[nc]++;
                }
                }
            }
        }
        /////sdasdas
     /*   for(it=a[c[p]].begin();it!=a[c[p]].end();++it)
{
ct++;
if (ct%2==1)nc=*it;
else {
r=*it;
if (v[c[p]]+r<v[nc]){
    v[nc]=v[c[p]]+*it;
    if (use[nc]==0){u++;c[u]=nc;use[nc]=1;if (apar[nc]>n)return 0;apar[nc]++;}
}
}
*/



        ////
    use[c[p]]=0;
    p++;
}
return 1;
}


int main()
{
 fscanf(f,"%d%d",&n,&m);
 for(i=1;i<=m;i++)
 {
  fscanf(f,"%d%d%d",&x,&y,&z);
  a[x].push_back(y);
  a[x].push_back(z);
 }

 if (belmann(1)==0)fprintf(g,"%s","Ciclu negativ!");
 else
  for(i=2;i<=n;i++)
   fprintf(g,"%d ",v[i]);
 fclose(g);
 return 0;
}