#include <cstdio>
#define buff_size 400001
#include<queue>
#include<vector>
#define INF 0x3f3f3f
using namespace std;

char buff[buff_size];
int pos=0, semn;
inline void read(int &nr){
    semn = 1;
    while(buff[pos] < '0' || buff[pos] > '9'){if(buff[pos]== '-' )semn = -1; if(++pos == 200000) fread(buff, 1, 200000, stdin), pos = 0;}
    nr = 0;
    while('0' <= buff[pos] && buff[pos] <= '9') {nr = nr * 10 + buff[pos] - '0';if(++pos == 200000) fread(buff, 1, 200000, stdin), pos = 0;}
    nr*=semn;
}
struct nod
{
    int y,c;
};
vector<vector<nod> > mat(50000);
vector<int> dist(50001,INF);
queue<int> q;
int n,i,x,y,c,m;

int main()
{
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    read(n);read(m);
    for(;m;--m)
    {
        read(x);read(y);read(c);
        mat[x].push_back( (nod) {y,c} );
    }
    dist[1]=0;
    q.push(1);

   while(!q.empty())
    {
        x=q.front();
        for(i=0;i<mat[x].size();++i)
            if( dist[ mat[x][i].y ] > dist[x]+ mat[x][i].c )
            {
                dist[mat[x][i].y]=dist[x]+mat[x][i].c;
                q.push(mat[x][i].y);
            }
            else
                if(dist[ mat[x][i].y ]>0 && dist[x]<0)
                {
                    printf("Ciclu negativ!");
                    return 0;
                }
        q.pop();
    }


    for (i=2;i<=n;i++)
            printf("%d ", dist[i] );
    return 0;
}