/* Bellman-ford implementation */
#include <fstream>
#include <vector>
#define VMAX 50002
#define infinite 100000000
using namespace std;

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

int n,m,s;

struct edge{
    int w;
    int to;
    edge *next;
};

edge* G[VMAX];
int dist[VMAX];
int pred[VMAX];

void add(struct edge **l, int n, int w)
{
    edge *p = new edge;
    p->to=n;
    p->w=w;
    p->next = *l;
    *l=p;
}

int bellman()
{
    
    // initializam graph-ul
    for(int i=1; i<=n; i++)
        dist[i]=infinite;
    dist[1]=0;
    
    // relaxam de |u-1| ori graph-ul
    for(int u=1; u<=n-1; u++)
        for(edge *p=G[u]; p; p=p->next){
            if(dist[u] + p->w < dist[p->to])
                dist[p->to] = dist[u] + p->w, pred[p->to]=u;
        }

    
    // verificam ciclurile negative
    for(int u=1; u<=n-1; u++)
        for(edge *p=G[u]; p; p=p->next)
            if(dist[u] + p->w < dist[p->to])
            {
                fout<<"Ciclu negativ!";
                return 0;
            }
    return 1;
}

void read()
{
    fin>>n>>m;
    for(int i=1; i<=m; ++i)
    {
        int a,b,c;
        fin>>a>>b>>c;
        add(&G[a], b, c);
    }
}

int main()
{
    read();
    if(bellman())
        for(int i=2; i<=n; ++i)
            fout<<dist[i]<<" ";
    
    return 0;
}