#include <iostream>
#include <fstream>
#define inf 1000000000
using namespace std;
int cost[50000], n, m, i, j;
struct muchii
{
    int a,b,c;
};
muchii x[250001];
int main()
{
    ifstream fin("bellmanford.in");
    ofstream fout("bellmanford.out");
    fin>>n>>m;
    for(i=1;i<=m;i++)
        fin>>x[i].a>>x[i].b>>x[i].c;
    cost[1]=0;
    for(i=2;i<=n;++i)
        cost[i]=inf;
    for(i=1;i<=n;i++)
        if(cost[x[i].a]+x[i].c>cost[x[j].b])
                fout<<"Ciclu negativ!"<<endl;
            else
                for(i=1;i<=n;i++)
                    for(j=1;j<=m;j++)
                        if(cost[x[j].a]+x[j].c<cost[x[j].b])
                            cost[x[j].b]=cost[x[j].a]+x[j].c;
    for (i=2; i<=n; i++)
        fout<<cost[i]<<' ';
    return 0;

}