#include<fstream>
#include<vector>
#include<iostream>
#include<iostream>
#include<stdlib.h>
#define lmic 51000
#define infinit 1000000

using namespace std;

struct muchie
{
    int inf;
    int cost;
}y;

vector<muchie>v[lmic];
int d[lmic];
int prezent[lmic];
int coada[1000000];
int aparitii[lmic];
ofstream g("bellmanford.out");

int bellmanford(int n)
{
    int prim,ultim,i,j,x,y;
    for(i=2;i<=n;i++)
    {
        d[i]=infinit;
    }
    cout<<"A";
    ultim=1;
    prim=1;
    coada[1]=1;
    while(prim<=ultim)
    {
        x=coada[prim++];
        aparitii[x]++;
        for(i=0;i<v[x].size();i++)
        {
            if(d[v[x][i].inf]>d[x]+v[x][i].cost)
            {
                if(prezent[v[x][i].inf]==0)
                {
                    coada[++ultim]=v[x][i].inf;
                    prezent[v[x][i].inf]==0;
                }
                aparitii[v[x][i].inf]++;
                d[v[x][i].inf]=d[x]+v[x][i].cost;
                if(aparitii[v[x][i].inf]>n)
                {
                    g<<"Ciclu negativ!";
                    return 0;
                }
            }
        }
        prezent[x]=0;
    }
    return 1;
}

int main()
{
    int n,m,a,i;
    ifstream f("bellmanford.in");
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>a>>y.inf>>y.cost;
        v[a].push_back(y);
    }

    if(bellmanford(n)==1)
    {
        for(i=2;i<=n;i++)
        {
            g<<d[i]<<" ";
        }
    }
}