#include <bits/stdc++.h>
#define Nmax 50001
#define INF 2e9+1
#define tip pair <int,int>
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
list <tip> G[Nmax];
queue <int> q;
bitset <Nmax> iq;
int nrap[Nmax];
int dist[Nmax];
int main()
{
    int n,m,i,j,k,cost;
    f>>n>>m;
    for(k=0;k<m;k++)
    {
        f>>i>>j>>cost;
        G[i].push_back({j,cost});
    }
    q.push(1);
    iq[1]=true;
    list <tip> :: iterator it;
    int x;
    fill(dist+2,dist+n+1,INF);
    while(!q.empty())
    {
        x=q.front();
        q.pop();
        iq[x]=false;
        for(it=G[x].begin();it!=G[x].end();it++)
            if(dist[it->first]>dist[x]+it->second)
            {
                dist[it->first]=dist[x]+it->second;
                if(!iq[it->first])
                {
                    if(nrap[it->first]>n)
                    {
                        g<<"Ciclu negativ!";
                        return 0;
                    }
                    else
                    {
                        q.push(it->first);
                        nrap[it->first]++;
                        iq[it->first]=true;
                    }
                }
            }
    }
    for(i=2;i<=n;i++)
        g<<dist[i]<<' ';

    return 0;
}