#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
vector<pair<int,int> > a[50001];
vector<pair<int,int> >::iterator it;
pair<int,int> p;
int i, n, m, x, y, costx, cost[50001], cd[50001], trc[50001];
bool sel[50001], neg=false;
int main(){
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d%d", &n, &m);
    for (i=1;i<=m;i++) {scanf("%d%d%d", &x, &y, &costx); a[x].push_back(make_pair(y, costx));}
    for (i=1;i<=n;i++) cost[i]=999999999;
    cd[1]=1; cd[0]=1; sel[1]=true; cost[1]=0;
    for (i=1;i<=cd[0] && !neg;i++) {
        for (it=a[i].begin();it!=a[i].end();it++) {
            p=*it;
            if ((!sel[p.first])&&(cost[p.first]>cost[i]+p.second)) {
                cd[++cd[0]]=p.first; cost[p.first]=cost[i]+p.second; sel[p.first]=true;
                trc[p.first]++; if (trc[p.first]>n) {printf("Ciclu negativ!\n"); return 0;}
            }
        }
        sel[i]=false;
    }
    for (i=2;i<=n;i++) printf("%d ", cost[i]);
    printf("\n"); return 0;
}