#include <bits/stdc++.h>
using namespace std;
ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");
int const lmax=5e4+7;
long long int const inf=1e18+7;
int n,m;
struct graph{
int node;
long long int cost;
};
long long int d[lmax];
vector<graph> G[lmax];
bool ok=true;
class cmp
{
public:
    bool operator()(graph a, graph b)
    {
        return a.cost>b.cost;
    }
};
priority_queue<graph,vector<graph>,cmp> pq;
void BellmanFord(int start)
{
    d[start]=0;
    pq.push({start,0});
    int iteratie=0;
    while(pq.empty()==false)
    {
        int node=pq.top().node;
        pq.pop();
        iteratie++;
        if(iteratie>m*(n-1))
        {
            ok=false;
            return ;
        }
        for(auto vec:G[node])
        {
            if(d[vec.node]>d[node]+vec.cost)
            {
                d[vec.node]=d[node]+vec.cost;
                pq.push({vec.node,d[vec.node]});
            }
        }
    }
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        d[i]=inf;
    }
    for(int i=0;i<m;i++)
    {
        int a,b;
        long long int c;
        fin>>a>>b>>c;
        G[a].push_back({b,c});
    }
    BellmanFord(1);
    if(ok==false)
    {
        fout<<"Ciclu negativ!";
    }
    else
    {
        for(int i=2;i<=n;i++)
        {
            fout<<d[i]<<" ";
        }
    }
    fin.close();
    fout.close();
    return 0;
}