#include<cstdio>
#include<vector>
#include<queue>
#include<utility>
#define N 50000
#define MULT 2000000000
using namespace std;

vector<pair<int,int> > vecin[N+1];
queue<int> Q;
int dist[N+1];
bool in_queue[N+1];
int viz[N+1];
int n;

bool adauga(int x){
    if (viz[x]==n) return false;
    viz[x]++;

    if (in_queue[x]==false){
        Q.push(x);
        in_queue[x]=true;
    }

    return true;
}

bool bellmanford(){
    adauga(1);
    dist[1]=0;

    while(!Q.empty()){
        int nod=Q.front();
        Q.pop();
        in_queue[nod]=false;

        for(int i=0;i<vecin[nod].size();i++){
            int now=vecin[nod][i].first;
            int cost=vecin[nod][i].second;

            if (dist[nod]+cost<dist[now]){
                dist[now]=dist[nod]+cost;
                if (!adauga(now)) return false;
            }
        }
    }

    return true;
}

int main(){
    freopen ("bellmanford.in","r",stdin);
    freopen ("bellmanford.out","w",stdout);
    int m,i;

    scanf ("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        int x,y,z;
        scanf ("%d%d%d",&x,&y,&z);

        vecin[x].push_back(make_pair(y,z));
    }

    for(i=1;i<=n;i++)
        dist[i]=MULT;

    if (!bellmanford()){
        printf ("Ciclu negativ!");
        return 0;
    }

    for(i=2;i<=n;i++)
        printf ("%d ",dist[i]);

    return 0;
}