#include <iostream>
#include<fstream>
#include<vector>
using namespace std;
struct Nod
{
    int x,cost ;
};
int n,m,q[100],d[100];
vector <Nod> L[100];
void Citire()
{
    int y,i;
    ifstream fin("bellmanford.in");
    Nod aux;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>y>>aux.x>>aux.cost;
        L[y].push_back(aux);
    }
}
int Bellmanford()
{
    int ul,pr,k,i;
    Nod aux;
    ul=pr=0;
    q[ul]=1;
    while(pr<=ul)
    {
        k=q[pr];
        pr++;
        int 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 i;
    for(i=1;i<=n;i++)
        d[i]=2000000000;
    d[1]=0;
}
int main()
{
    ofstream fout("bellmanford.out");
    Citire();
    Initializare();
    int ciclu,i;
    ciclu=Bellmanford();
    if(!ciclu)
    {
        fout<<"Ciclu negativ!";
        fout<<"\n";
        fout.close();
        return 0;
    }
    for(i=2;i<=n;i++)
        fout<<d[i]<<" ";
    fout<<"\n";
    fout.close();
    return 0;
}