#include <fstream>
#include <queue>
#include <vector>
#include <bitset>

#define MAX 50005
#define INF 0x3f3f3f3f

using namespace std;

int n, m, dist[MAX], ap[MAX];
vector< pair < int , int > > v[MAX];
queue< int > q;
bitset< MAX > inQueue;

bool bford()
{
    while(!q.empty())
    {
        int nod = q.front(); q.pop(); inQueue[nod] = false;
        for(vector< pair < int , int > >::iterator it = v[nod].begin(); it != v[nod].end(); it++)
        {
            if(dist[it->first] > dist[nod] + it->second)
            {
                dist[it->first] = dist[nod] + it->second;
                if(!inQueue[it->first])
                {
                    q.push(it->first); inQueue[it->first] = true; ap[it->first]++;
                    if(ap[it->first] > n) return false;
                }
            }
        }
    }return true;
}

int main()
{
    ifstream in("bellmanford.in"); in>>n>>m; int a, b, c; while(m--) {in>>a>>b>>c; v[a].push_back(make_pair(b, c));} in.close();
    for(int i = 2; i <= n; i++) dist[i] = INF; dist[1] = 0; q.push(1); inQueue[1] = true;
    ofstream out("bellmanford.out");
    if(bford()) for(int i = 2; i <= n; i++) out<<dist[i]<<" ";
    else out<<"Ciclu negativ!\n"; out.close();
    return 0;
}