#include <bits/stdc++.h>
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
vector< vector< pair<int,int> > > a;
vector<int> d;
vector<int> c;
vector<bool> use;
queue<int> q;
int main()
{
    int n,m,x,y,z;
    in>>n>>m;
    a=vector< vector< pair<int,int> > >(n+1);
    d=vector<int>(n+1,numeric_limits<int>::max());
    use=vector<bool>(n+1);
    c=vector<int>(n+1);
    for(;m;m--)
    {
        in>>x>>y>>z;
        a[x].push_back({y,z});
        a[y].push_back({x,z});
    }
    q.push(1);
    d[1]=0;
    c[1]++;
    use[1]=true;
    while(!q.empty())
    {
        int k=q.front();q.pop();
        use[k]=false;
        for(auto i: a[k])
        if(d[k]+i.second < d[i.first])
        {
            d[i.first]=d[k]+i.second;
            if(c[i.first]>n)
            {
                out<<"Ciclu negativ!";
                return 0;
            }
            c[i.first]++;
            if(use[i.first]==false)
            {
                q.push(i.first);
                use[i.first]=true;
            }
        }
    }
    for(int i=2;i<=n;i++)out<<d[i]<<' ';
    return 0;
}