#include <bits/stdc++.h>

using namespace std;

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

int n,m;
vector <pair <int,int>> adiacenta[50010];
int fr[50000],d[5000];
vector<bool>vizitat;
queue <int>q;
bool ok;

void BF(int i)
{
    d[i] = 0;
    vizitat[i] = true;
    q.push(i);

    while(!q.empty())
    {
        int vf = q.front();
        q.pop();
        vizitat[vf] = false;
        fr[vf]++;
        if(fr[vf] > n)
        {
            out<<"Ciclu negativ!\n";
            ok = false;
            return;

        }
        else
        {
            for (auto vecin:adiacenta[vf])
            {

                if(d[vecin.first] > vecin.second + d[vf])
                {
                    d[vecin.first] = vecin.second + d[vf];
                    if(!vizitat[vecin.first])
                    {
                        q.push(vecin.first);
                    }

                }
            }

        }
    }


}

int main()
{

    int x,y,c;
    in>>n>>m;

    for(int i = 1; i <= n; i++)
        d[i] = 2e9;

    for(int i = 1; i <= m; i++)
    {

        in>>x>>y>>c;
        adiacenta[x].push_back(make_pair(y,c));//graf orientat
    }

    vizitat.assign(n+1,false);
    ok = true;
    BF(1);

    if(ok)
    {
        for(int i = 2; i<= n; i++)
        {
            out<<d[i]<<" ";
        }
    }
    out<<"\n";

    return 0;
}