#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#define inf 0x3f3f3f3f
#define nmax 50001
using namespace std;

struct muchie{
    int y;
    int c;
};

vector <muchie> g[nmax];
queue <int> Q;
int itnod[nmax],cost[nmax];
bool used[nmax];

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    int i,n,m,x,y,nod,c;
    scanf("%d %d",&n,&m);
    for (i=1;i<=m;i++)
    {
        scanf("%d %d %d",&x,&y,&c);
        g[x].push_back((muchie){y,c});
    }
    memset(used, false, sizeof(used));
    memset(cost, inf, sizeof(cost));
    cost[1]=0;
    memset(itnod, 0, sizeof(itnod));
    Q.push(1);
    while(!Q.empty())
    {
        nod=Q.front();
        Q.pop();
        used[nod]=false;
        for (i=0;i<g[nod].size();i++)
            if (cost[ g[nod][i].y ]> cost[nod]+g[nod][i].c)
            {
                cost[ g[nod][i].y ]= cost[nod]+g[nod][i].c;
                if (!used[ g[nod][i].y ])
                {
                    Q.push(g[nod][i].y);
                    used[ g[nod][i].y ]=true;
                    if (++itnod[ g[nod][i].y ]>n)
                    {
                        printf("Ciclu negativ!\n");
                        return 0;
                    }
                }
            }
    }
    for (i=2;i<=n;i++)
        printf("%d ",cost[i]);
    return 0;
}