#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n,m;
const int max_n=50005;
const int inf=2000000000;
struct nod
{
    int c,vf;
    nod(int c=0, int vf=0):
        c(c),vf(vf)
    {
    }
};
vector < vector <nod> >a;
queue <int>q;
vector <int> d(max_n,inf),cnt(max_n,0);
vector <bool> inv(max_n,0);
bool ciclu;
void citire()
{
    fin>>n>>m;
    int x,y,z;
        a.resize(n+1);
    for(int i=1;i<=m;i++)
        {
            fin>>x>>y>>z;
            a[x].push_back(nod(z,y));
        }

}
void rez()
{
    q.push(1);
    inv[1]=1;
    d[1]=0;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        inv[x]=0;
        vector <nod>::iterator it;
        for(it=a[x].begin();it!=a[x].end();it++)
            if(d[it->vf]>d[x]+it->c)
                {
                    d[it->vf]=d[x]+it->c;
                    if(!inv[it->vf])
                    {
                        if(cnt[it->vf]>n)
                        {
                            ciclu=1;
                            return;
                        }
                        inv[it->vf]=1;
                        q.push(it->vf);
                        cnt[it->vf]++;
                    }
                }
    }
}
int main()
{
    citire();
    rez();
    if(ciclu)
    {
        fout<<"Ciclu negativ!";
    }
    else
    {

        for(int i=2;i<=n;i++)
            {
                fout<<d[i]%inf<<' ';
                }
    return 0;
}