#include <bits/stdc++.h>
#define Nmax 50001
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
list < pair <int,int> > G[Nmax];
bitset <Nmax> inq;
queue <int> q;
int nrap[Nmax];
int d[Nmax];
int n,m;
void Bellman_Ford()
{
    fill(d+2,d+n+1,Nmax);
    int x;
    q.push(1);
    while(!q.empty())
    {
        x=q.front();
        q.pop();
        inq[x]=false;
        for(const auto &it:G[x])
            if(d[it.first]>d[x]+it.second)
            {
                d[it.first]=d[x]+it.second;
                if(!inq[it.first])
                {
                    if(nrap[it.first]>n)
                    {
                        g<<"Ciclu negativ!";
                        exit(0);
                    }
                    nrap[it.first]++;
                    inq[it.first]=true;
                    q.push(it.first);
                }
            }
    }
}
int main()
{
    int i,j,k;
    f>>n>>m;
    while(m--)
    {
        f>>i>>j>>k;
        G[i].push_back({j,k});
    }
    Bellman_Ford();
    for(i=2;i<=n;i++)
        g<<d[i]<<' ';

    return 0;
}