#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
vector< pair<int,int> >v[50002];
queue <int> coad;
int n,m,i,j,val,oki,dist[50002],viz[50002],vizc[50002];
int bellmanford()
{
    int x,cnt,i,j,y,cost;
    dist[1]=0;
    for(int i=2;i<=n;i++)
        dist[i]=9999999;
    coad.push(1);
    vizc[1]=1;
    while(!coad.empty())
    {
        x=coad.front();
        viz[x]++;
        coad.pop();
        vizc[x]=0;
        if(viz[x]>=n)
            return 0;
        for(int i=0;i<v[x].size();i++)
        {
            y=v[x][i].first;
            cost=v[x][i].second;
            if(dist[y]>dist[x]+cost)
                    {
                        dist[y]=dist[x]+cost;
                        if(vizc[y]==0)
                            {
                                coad.push(y);
                                vizc[y]=1;
                            }
                    }
        }
    }
    return 1;
}
int main()
{
    fin>>n>>m;
    for(int l=1;l<=m;l++)
    {
        fin>>i>>j>>val;
        v[i].push_back(make_pair(j,val));
    }
    if(bellmanford())
    {
        for(i=2;i<=n;i++)
            fout<<dist[i]<<' ';
    }
    else
        fout<<"Ciclu negativ!";
    return 0;
}