#include <bits/stdc++.h>
#define NMAX 50005
using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

vector <pair <int,int> >v[NMAX];
int check[NMAX],c[NMAX],d[NMAX],aparitii[NMAX];
int n,m;

void bellman(int x)
{
    int p,u,j;
    p=u=1; c[x]=x; d[x]=0; check[x]=1; aparitii[x]=1;
    while(p<=u)
    {
        j=c[p++];
        for(auto i:v[j])
        {
            if(d[j]+i.second<d[i.first])
            {
                d[i.first]=d[j]+i.second;
                if(!check[i.first])
                {
                    c[++u]=i.first;
                    check[u]=1;
                    aparitii[i.first]++;
                }
            }
        }
        if(aparitii[j]>=n) {fout<<"Ciclu negativ!"; return ;}
    }
}

int main()
{
    int i,x,y,z;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>z;
        v[x].push_back({y,z});
    }
    for(i=1;i<=n;i++)
    {
        d[i]=INT_MAX;
    }
    bellman(1);
    for(i=2;i<=n;i++)
    {
        fout<<d[i]<<" ";
    }
    return 0;
}