#include <cstdio>
#include <vector>
#include <deque>
#define INF 2000000000
using namespace std;
vector <pair <int,int> > v[50001];
deque <int> dq;
int c[50001],f[50001],apc[50001];
int main()
{
    FILE *fin=fopen ("bellmanford.in","r");
    FILE *fout=fopen ("bellmanford.out","w");
    int n,m,i,nod,vecin,x,y,cst;
    fscanf (fin,"%d%d",&n,&m);
    for (i=1;i<=m;i++){
        fscanf (fin,"%d%d%d",&x,&y,&cst);
        v[x].push_back(make_pair (y,cst));
    }
    for (i=2;i<=n;i++)
        c[i]=INF;
    dq.push_back(1);
    f[1]=1;
    apc[1]=1;
    while (dq.size()){
        nod=dq.front();
       // printf ("%d ",nod);
        for (i=0;i<v[nod].size();i++){
            vecin=v[nod][i].first;
            if (c[nod]+v[nod][i].second<c[vecin]){
                c[vecin]=c[nod]+v[nod][i].second;
                if (!f[vecin]) {// nu e in deque
                    f[vecin]=1;
                    apc[vecin]++;
                    dq.push_back(vecin);
                }
                if (apc[vecin]==n){
                    fprintf (fout,"Ciclu negativ!");
                    return 0;
                }
            }
        }
        f[nod]=0;
        dq.pop_front();
    }
    for (i=2;i<=n;i++)
        fprintf (fout,"%d ",c[i]);
    return 0;
}