#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int N=50000,INF=1000;
class To{
    public:
        int v,c;
        To(){
        }
        To(int vv,int cc){
            v=vv;
            c=cc;
        }
};
int dist[N+1];
vector<To>g[N+1];
bool queued[N+1];
queue<int>q;
int n,m,lim;
void lol(){
    int x=0;
    x++;
}
void bellman_ford(){
    q.push(1);
    queued[1]=true;
    for(int i=2;i<=n;i++)
        dist[i]=INF*N+1;
    bool neg=false;
    while(!q.empty()&&!neg){
        int dad=q.front();
        if(dad==5)
            lol();
        for(unsigned int i=0;i<g[dad].size();i++){
            To son=g[dad][i];
            if(dist[son.v]>dist[dad]+son.c){
                dist[son.v]=dist[dad]+son.c;
                if(dist[son.v]<lim){
                    neg=true;
                    break;
                }
                if(!queued[son.v]){
                    q.push(son.v);
                    queued[son.v]=true;
                }
            }
        }
        q.pop();
        queued[dad]=false;
    }
    if(neg)
        printf("Ciclu negativ!");
    else
        for(int i=2;i<=n;i++)
            printf("%d ",dist[i]);
}
int min2(int a,int b){
    if(a<b)
        return a;
    return b;
}
int main(){
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d%d",&n,&m);
    lim=INF+1;
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%dd",&x,&y,&z);
        lim=min2(lim,z);
        g[x].push_back(To(y,z));
        g[y].push_back(To(x,z));
    }
    lim*=n;
    bellman_ford();
    return 0;
}