#include <cstdio>
#include <vector>
#include <queue>

using namespace std;
#define MAX 50005
#define INF 50000001


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