#include<fstream>
#include<queue>
using namespace std;

struct nod
{
    int vecin,cost;
};

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

const int oo=1<<30;
const int NMAX=50005;

int n,m;
vector<nod>v[NMAX];
int dist[NMAX],frecv[NMAX];
queue<nod>Q;

inline void Citire()
{
    int i,x,y,z;
    nod k;
    fin>>n>>m;
    for (i=1;i<=n;i++)
        {
            fin>>x>>y>>z;
            k.vecin=y;
            k.cost=z;
            v[x].push_back(k);
        }
    dist[1]=0;
    for (i=2;i<=n;i++) dist[i]=oo;
}

inline void Afisare()
{
    int i;
    for (i=2;i<=n;i++)
        if (dist[i]!=oo) fout<<dist[i]<<"\n";
        else fout<<"0\n";
}

inline void BELLMANFORD()
{
    int i,len,x,costarico;
    bool test=0;
    nod k;
    k.vecin=1;
    k.cost=0;
    Q.push(k);
    while (!Q.empty() && !test)
        {
            x=Q.front().vecin;
            costarico=Q.front().cost;
            Q.pop();
            frecv[x]++;
            if (frecv[x]<n)
                {if (costarico==dist[x])
                    {
                        len=v[x].size();
                        for (i=0;i<len;i++)
                            if (dist[v[x][i].vecin]>dist[x]+v[x][i].cost)
                                {
                                    dist[v[x][i].vecin]=dist[x]+v[x][i].cost;
                                    k.vecin=v[x][i].vecin;
                                    k.cost=dist[v[x][i].vecin];
                                    Q.push(k);
                                }
                    }
                }
            else test=1;
        }
    if (!test) Afisare();
    else fout<<"Ciclu negativ!\n";
}

int main()
{
    Citire();
    BELLMANFORD();
    return 0;
}