#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
FILE *in,*out;
struct edge
{
    int target;
    short int cost;
}vertex;
struct list
{
    vector<edge>v;
}adjlist[50001];
const int inf=2000000000;
int n,edges,dist[50001],nr[50001];
bool mark[50001];
vector<edge>::iterator it;
queue<int>q;
int main()
{
    in=fopen("bellmanford.in","r");
    out=fopen("bellmanford.out","w");
    int i,here,x;
    fscanf(in,"%d%d",&n,&edges);
    for(i=1;i<=edges;++i)
    {
        fscanf(in,"%d%d%hd",&x,&vertex.target,&vertex.cost);
        adjlist[x].v.push_back(vertex);
    }
    for(i=1;i<=n;++i)dist[i]=inf;
    dist[1]=0;
    q.push(1);
    mark[1]=1;
    while(!q.empty())
    {
        here=q.front();
        mark[here]=0;
        for(it=adjlist[here].v.begin();it!=adjlist[here].v.end();++it)if(dist[here]<inf&&dist[(*it).target]>dist[here]+(*it).cost)
        {
            dist[(*it).target]=dist[here]+(*it).cost;
            if(!mark[(*it).target])
            {
                if(nr[(*it).target]>n)
                {
                    fprintf(out,"Ciclu negativ!\n");
                    return 0;
                }
                else
                {
                    q.push((*it).target);
                    mark[(*it).target]=1;
                    ++nr[(*it).target];
                }
            }
        }
        q.pop();
    }
    for(i=2;i<=n;++i)fprintf(out,"%d ",dist[i]);
    fclose(in);fclose(out);
    return 0;
}