// Bellman - O(N*M)
#include <fstream>
#include <vector>
#include <deque>
#include <bitset>
#define Nmax 50009
#define y first
#define c second
#define oo 2000000000
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
typedef pair<int,int> edge;
int N,M,d[Nmax],used[Nmax],x,y,c;
vector < edge > G[Nmax];
deque < int > Q;
bitset < Nmax > inQ;

int Bellmanford(int S)
{
    for(int i=1;i<=N;++i)d[i]=oo;
    d[S]=0; inQ[S]=1;
    for(Q.push_back(S);  !Q.empty();  Q.pop_front())
    {
        int node=Q.front();
        inQ[node]=0 , ++used[node];
        if (used[node]==N) return 0;
        for (vector<edge>::iterator it=G[node].begin();it!=G[node].end();++it)
            if(d[it->y] > d[node]+it->c)
            {
                d[it->y]=d[node]+it->c;
                if (!inQ[it->y]) Q.push_back(it->y), inQ[it->y]=1;
            }
    }
    return 1;
}

int main()
{
    f>>N>>M;
    for(int i=1;i<=M;++i)
        f>>x>>y>>c, G[x].push_back(edge(y,c));
    if(!Bellmanford(1))g<<"Ciclu negativ!"<<'\n';
        else
        {
            for(int i=2;i<=N;++i)g<<d[i]<<' ';
            g<<'\n';
        }
    f.close();g.close();
    return 0;
}