#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
#define pb push_back
#define Nmax 50001
using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

int n,m,nr[Nmax],x,y,c,mn[Nmax];
struct edge{
    int nod,val;
}crt;
vector<edge> V[Nmax],H;

bool comp(edge a,edge b)
{
    return a.val>b.val;
}

int main()
{
    f>>n>>m;
    for (int i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        crt.nod = y;
        crt.val = c;
        V[x].pb(crt);
    }


    memset(mn,0x3f,sizeof(mn));
    crt.nod = 1;
    crt.val = 0;
    H.pb(crt);
    mn[1] = 0;
    while (!H.empty())
    {
        crt = H[0];
        pop_heap(H.begin(),H.end(),comp);
        H.pop_back();
        for (int i=0;i<V[crt.nod].size();i++)
        {
            if (mn[V[crt.nod][i].nod]>crt.val + V[crt.nod][i].val)
            {
                nr[V[crt.nod][i].nod]++;
                if (nr[V[crt.nod][i].nod]>=n)
                {
                    g<<"Ciclu negativ!\n";
                    return 0;
                }
                mn[V[crt.nod][i].nod] = crt.val + V[crt.nod][i].val;
                H.push_back(V[crt.nod][i]);
                H.back().val = mn[V[crt.nod][i].nod];
                push_heap(H.begin(),H.end(),comp);
            }
        }
    }

    for (int i=2;i<=n;i++)
        g<<mn[i]<<' ';

    return 0;
}