#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int N=50000,INF=1000;
class To{
    public:
        int v,c,nrv;
        To(){
        }
        To(int vv,int cc){
            v=vv;
            c=cc;
            nrv=0;
        }
};
int dist[N+1];
vector<To>g[N+1];
bool queued[N+1];
queue<int>q;
int n,m;
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();
        for(unsigned int i=0;i<g[dad].size();i++){
            To son=g[dad][i];
            if(dad==5&&son.v==3)
                lol();
            if(dist[son.v]>dist[dad]+son.c)
                if(son.nrv>n){
                    neg=true;
                    break;
                }
                else{
                    g[dad][i].nrv++;
                    if(!queued[son.v])
                        q.push(son.v);
                    dist[son.v]=dist[dad]+son.c;
                    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 main(){
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%dd",&x,&y,&z);
        g[x].push_back(To(y,z));
        g[y].push_back(To(x,z));
    }
    bellman_ford();
    return 0;
}