#include <cstdio>
#define buff_size 400001
#include<queue>
#include<vector>
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;
}
queue <int> q;
vector <int> a[50001],c[50001];
int d[50001],w[500001],i,n,m,x,y,z,j;

int main()
{
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    read(n);read(m);
    for (i=1;i<=m;i++)
    {
        read(x);read(y);read(z);
        a[x].push_back(y);
        c[x].push_back(z);
    }
    for (i=2;i<=n;i++)
        d[i]=1 << 30;
    q.push(1);
    while (!q.empty())
    {
        x=q.front();
        w[x]++;
        if (w[x]>n) {printf("Ciclu negativ!");return 0;}
        for (j=0;j<a[x].size();j++)
            if (d[x]+c[x][j]<d[a[x][j]])
            {
                d[a[x][j]]=d[x]+c[x][j];
                q.push(a[x][j]);
            }
        q.pop();
    }
    for (i=2;i<=n;i++)
            printf("%d ", d[i] );
    return 0;
}