#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
struct str {int c; int urm;} t;
bool incoada[50005];
int ncoada[50005],n;
vector <str> g[50005];
int cost[50005];
queue <int > q;
int bellmanford(int nd)
{
    int t,T;
    q.push(nd);
    incoada[nd]=1;
    cost[1]=0;
    while(!q.empty())
    {
        t=q.front();
        q.pop();
        incoada[t]=0;
        vector < str >::iterator i;
        for(i=g[t].begin();i!=g[t].end();i++)
        if(cost[t]<(1<<30))
        {
            if(cost[i->urm]>cost[t]+i->c)
            {
                cost[i->urm]=cost[t]+i->c;
                if(incoada[i->urm]==0)
                {
                    if(ncoada[i->urm]>n)
                        return 0;
                    else
                    {
                        q.push(i->urm);
                        incoada[i->urm]=1;
                        ncoada[i->urm]++;
                    }
                }
            }
        }
    }
    return 1;
}

int main()
{int m,i,cc,y,x;
str t;
in>>n>>m;
for(i=1;i<=m;i++)
{
    in>>x>>y>>cc;
    t.urm=y;
    t.c=cc;
    g[x].push_back(t);
}
for(i=1;i<=n;i++)
{
    cost[i]=(1<<30);
}
if(bellmanford(1)==0)
{
    out<<"Ciclu negativ!"<<'\n';
}
else
for(i=2;i<=n;i++)
{
    out<<cost[i]<<" ";
}
    return 0;
}