#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<deque>
#define Nmax 50009
#define pb push_back
#define mp make_pair
#define inf 0x3f3f3f
#define nod first
#define cost second

using namespace std;

vector<pair<int,int> > a[Nmax];
vector<pair<int,int> >::iterator it;
deque<int> Q;
int n,m,i,x,y,c,D[Nmax],ok[Nmax],nr[Nmax];

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);

    scanf("%d%d",&n,&m);
    for (i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        a[x].push_back(mp(y,c));
    }
    memset(D,inf,sizeof(D));
    D[1]=0;
    Q.pb(1);
    ok[1]=1;

    while (!Q.empty())
    {
        x=Q.front();
        nr[x]++;
        for (it=a[x].begin();it!=a[x].end();it++)
            if (D[x]+(*it).cost<D[(*it).nod] && !ok[i])
            {
                if (nr[(*it).nod]>n)
                {
                    printf("Ciclu negativ!\n");
                    return 0;
                }
                D[(*it).nod]=D[x]+(*it).cost;
                ok[(*it).nod]=1;
                Q.pb((*it).nod);
            }
        ok[x]=0;
        Q.pop_front();
    }
    for (i=2;i<=n;i++)
        printf("%d ",D[i]);
}