#include <bits/stdc++.h>
#define dim 250002
#define int long long
using namespace std;
ifstream fin ("bellmanford.in");
ofstream fout("bellmanford.out");
const int inf=100000000000;
int n,sol[dim],viz[dim];

struct el
{
    int nod,cost;
};
queue<el>coada;
vector<el> a[dim];

void bellmanford ()
{
    while (!coada.empty())
    {
        el x=coada.front();
        coada.pop();
        for (auto y:a[x.nod])
            if (x.cost+y.cost<sol[y.nod])
            {
                viz[y.nod]++;
                if (viz[y.nod]>n+1)
                {
                    fout<<"Ciclu negativ!";
                    exit(0);
                }
                sol[y.nod]=x.cost+y.cost;
                coada.push({y.nod,sol[y.nod]});
            }
    }
}

void Solve ()
{
    int i,m,x,y,z;
    fin>>n>>m;
    for (i=2;i<=n;i++)
        sol[i]=inf;
    while (m--)
    {
        fin>>x>>y>>z;
        a[x].push_back({y,z});
    }
    coada.push({1,0}),viz[1]=1;
    bellmanford();
    for (i=2;i<=n;i++)
        fout<<sol[i]<<' ';
}

int32_t main()
{
    int t=1;
    while (t--)
    {
        Solve();
    }
    return 0;
}