#include <cstdio>
#include <vector>
#include <queue>
#define MAX 50001
#define INF 2000000000

using namespace std;

vector <pair<int,int>> lista[MAX];
queue <int> q;
int n,m,d[MAX],cate[MAX];
int bellman(int sursa);
int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    int i,x,y,w;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&w);
        lista[x].push_back(make_pair(y,w));
    }
    if(!bellman(1))
        printf("Ciclu negativ!");
    else
        for(i=2;i<=n;++i)
            printf("%d ",d[i]);
    return 0;
}
int bellman(int sursa)
{
    int i,x,y,w;
    for(i=1;i<=n;++i)
        d[i]=INF;
    d[sursa]=0,q.push(sursa);
    while(!q.empty())
    {
        x=q.front();
        q.pop();
        cate[x]++;
        if(cate[x]==n)return 0;
        for(i=0;i<lista[x].size();++i)
        {
            y=lista[x][i].first;
            w=lista[x][i].second;
            if(d[y]>d[x]+w)
            {
                d[y]=d[x]+w;
                q.push(y);
            }
        }
    }
    return 1;
}