#include <fstream>
#include <list>
#include <queue>
#include <climits>

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

const int nmax=50005, INF=INT_MAX;
int n, m, negative_cycle=0;
int in_pq[nmax], dist[nmax], vis[nmax];

list <pair <int, int> >g[nmax];

struct comparator
{
    bool operator()(const int &a,  const int &b) const
    {
        return dist[a]>dist[b];
    }
};

void read_data()
{
    int i, x, y, c;

    fin>>n>>m;

    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        g[x].push_back(make_pair(y,c));
    }
}
void dijkstra(int node)
{
    priority_queue<int, vector<int>, comparator>pq;
    list <pair <int, int> > :: iterator it;
    int i, new_node, cost;

    for(i=1;i<=n;i++)
        dist[i]=INF;

    in_pq[node]=1;
    dist[1]=0;

    pq.push(node);

    while(!pq.empty() && !negative_cycle)
    {
        node=pq.top();
        pq.pop();
        in_pq[node]=0;

        for(it=g[node].begin();it!=g[node].end();it++)
        {
            new_node=(*it).first;
            cost=(*it).second;
            if(dist[new_node]>dist[node]+cost)
            {
                dist[new_node]=dist[node]+cost;
                if(!in_pq[new_node])
                {
                    pq.push(new_node);
                    in_pq[new_node]=1;
                    vis[new_node]++;
                }
                if(vis[new_node]>=n)
                    negative_cycle=1;
            }
        }
    }
}
void print()
{
    int i;

    if(negative_cycle)
            fout<<"Ciclu negativ!";
    else
        for(i=2;i<=n;i++)
            fout<<dist[i]<<' ';
}
int main()
{
    read_data();
    dijkstra(1);
    print();
}