#include <fstream>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

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

bool NEGATIVE ();

unsigned int N, M;
unsigned int x[250001], y[250001];
int c[250001];

vector <unsigned int> G[50001];
vector < pair <int, unsigned int> > H;
pair <int, unsigned int> PR;
bool seen[50001];
unsigned long long int step;
unsigned int pos, node;
unsigned int i, j;

int cost[50001];

int main ()
{
    fin >> N >> M;
    for (i=1; i<=M; i++)
    {
        fin >> x[i] >> y[i] >> c[i];
        G[x[i]].push_back(i);
    }
    for (i=2; i<=N; i++)
        cost[i] = INT_MAX;
    H.push_back(make_pair(0,1));
    make_heap(H.begin(),H.end());
    while (H.size() && step<=1LL*N*M)
    {
        step++;
        pop_heap(H.begin(),H.end());
        PR = H.back();
        node = PR.second;
        seen[node] = 0;
        for (j=0; j<G[node].size(); j++)
        {
            pos = G[node][j];
            if (cost[y[pos]] > cost[x[pos]] + c[pos])
            {
                cost[y[pos]] = cost[x[pos]] + c[pos];
                if (!seen[y[pos]])
                {
                    seen[y[pos]] = 1;
                    H.push_back(make_pair(-cost[y[pos]],y[pos]));
                    push_heap(H.begin(),H.end());
                }
            }
        }
    }
    if (NEGATIVE() == 1)
    {
        fout << "Ciclu negativ!\n";
        return 0;
    }
    for (i=2; i<=N; i++)
        fout << cost[i] << ' ';
    return 0;
}

bool NEGATIVE ()
{
    for (i=1; i<=M; i++)
        if (cost[x[i]]+c[i] < cost[y[i]])
            return 1;
    return 0;
}