#include <fstream>
#include <math.h>
#include <set>
#include <queue>

using namespace std;

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

unsigned long long k;

int dist[50001], n, m, f[50001];

vector <pair <int, int>> l[50001];

struct muchie{
    int x, y, c;
}muchii[250001];

int bellman_ford(int nod)
{
    int i, p, u, nod2, ok = 1, nod1, c, coada[50001];

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

    p = u =1;
    coada[p] = nod;
    dist[nod] = 0;

    while (p<= u)
    {
        nod1 = coada[p];
        f[nod1]++;
        if(f[nod1] >= n)
            ok = 0;
        else
        {
            for (i = 0; i< l[nod1].size(); i++)
            {
                nod2 = l[nod1][i].first;
                c = l[nod1][i].second;
                if(dist[nod1] + c < dist[nod2])
                {
                    dist[nod2] = dist[nod1] + c;
                    u++;
                    coada[u] = nod2;
                }
            }
        }
        p++;

    }

    return ok;
}

//int bellman_ford()
//{
//    int i, j, ok;
//
//    for (j  = 1; j<= n-1; j++)
//    {
//        for (i = 1; i<= m; i++)
//        if(dist[muchii[i].x] + muchii[i].c < muchii[i].y)
//            muchii[i].y = dist[muchii[i].x] + muchii[i].c;
//    }
//
//    ok = 1;
//    for (i = 1; i<= m; i++)
//        if(dist[muchii[i].x] + muchii[i].c < muchii[i].y)
//        {
//            ok = 0;
//        }
//    return ok;
//}

int main()
{
    int x, y, c, i;
    fin >> n >> m;
    for (i =1; i<= m; i++)
    {
        fin >> x >> y >> c;
        l[x].push_back({y, c});
        l[y].push_back({x, c});
    }
    
    if (bellman_ford(1) == 0)
    {
        fout << "Ciclu negativ!";
        return 0;
    }
    else
    {
        for (i = 2; i<= n; i++)
        fout << dist[i] << " ";
    }
}