#include <fstream>
#include <cstdlib>
#include <vector>
#include <queue>
#include <bitset>
#define inf 1<<30
#define maxn 50010

using namespace std;
bitset<maxn> inqueue;
queue<int> q;
int cnt[maxn];
vector<pair<int,int> > a[maxn];
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
int n,m;
int d[maxn];

void read()
{
    in>>n>>m;
    int x,y,z;
    for(int i=1;i<=m;i++)
    {
        in>>x>>y>>z;
        a[x].push_back(make_pair(y,z));
    }
}

void bellman()
{
    d[1]=0;
    q.push(1);
    while(!q.empty())
    {
        int nod=q.front();
        q.pop();
        inqueue[nod]=0;
        for(int i=0;i<a[nod].size();i++)
        {
            int nodc=a[nod][i].first;
            if(d[nodc]>d[nod]+a[nod][i].second)
            {
                d[nodc]=d[nod]+a[nod][i].second;
                if(inqueue[nodc]==0)
                {
                    inqueue[nodc]=1;
                    q.push(nodc);
                    cnt[nodc]++;
                    if(cnt[nodc]>n) {out<<"Ciclu negativ!";exit(0);}
                }
        }
    }
    }
}
int main()
{
    read();
    for(int i=1;i<=n;i++) d[i]=inf;
    bellman();
    for(int i=2;i<=n;i++)
    out<<d[i]<<" ";

    return 0;
}