#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;
int n,m,q[50000],d[50000];
struct Nod
{
    int x,cost;
};
vector <Nod> L[50000];

void Citire()
{
    Nod aux;
    int y,i;
    ifstream fin("bellmanford.in");
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>y>>aux.x>>aux.cost;
        L[y].push_back(aux);
    }
    fin.close();
}

int BellmanFord(int S)
{
    int ul,pr,k,i,N;
    Nod aux;
    pr = ul = 0;
    q[ul] = S;
    while(pr<=ul)
    {
        k = q[pr++];
        N = L[k].size();
        for(i=0;i<N;i++)
        {
            aux = L[k][i];
            if(d[aux.x]>d[k]+aux.cost)
            {
                d[aux.x]=d[k]+aux.cost;
                q[++ul]=aux.x;
                if(d[aux.x]>d[k]+aux.cost) return 0;
            }
        }
    }
    return 1;
}

void Initializare(int S)
{
    int infinit=2000000000;
    for(int i=1;i<=n;i++)
        d[i]=infinit;
    d[S]=0;
}

int main()
{
    Citire();
    Initializare(1);
    ofstream fout("bellmanford.out");
    if(!BellmanFord(1))
    {
        fout<<"Ciclu negativ!";
        fout.close();
        return 0;
    }
    for(int i=2;i<=n;i++) fout<<d[i]<<" ";
    fout.close();
    return 0;
}