#include <fstream>
#include <vector>
#include <queue>
#define NMAX 50002
#define INF 500000000

using namespace std;

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

struct da{
    int z, cost;
};
int n, start = 1, m;
int cmin[NMAX]; ///cmin[x] = costul drumului de cost minim de la start la x
int nr[NMAX]; ///nr[x] = de cate ori a fost actualizat costul drumului
vector <da> v[NMAX];
queue <int> C;

void citire();
bool bellman_ford();

int main ()
{
    int i;
    citire();
    if (!bellman_ford())
        fout << "Ciclu negativ!";
    else
        for (i = 2; i <= n; i++)
            fout << cmin[i] << ' ';
    return 0;
}
void citire()
{
    int i, x, y, c;
    fin >> n >> m;
    da aux;
    for (i = 0; i < m; i++)
    {
        fin >> x >> y >> c;
        aux.z = y;
        aux.cost = c;
        v[x].push_back(aux);
    }
}
bool bellman_ford()
///returnam 0 daca nu exista solutie
///1 daca exista solutie
{
    int i, vf;
    ///initializare
    for (i = 1; i <= n; i++)
        cmin[i] = INF;
    cmin[start] = 0;
    C.push(start);
    while (!C.empty())
    {
        vf = C.front();
        C.pop();
        ///parcurg lista de adiacenta a lui x
        for (i = 0; i < v[vf].size(); i++)
            if (cmin[v[vf][i].z] > cmin[vf] + v[vf][i].cost)
            {
                cmin[v[vf][i].z] = cmin[vf] + v[vf][i].cost;
                nr[v[vf][i].z]++;
                if ( nr[v[vf][i].z] == 0) return 0;
                C.push(v[vf][i].z);
            }
    }
    return 1;
}