#include <cstdio>
#include <vector>
#include <queue>
#include <utility>
#define NMAX 50005
#define INFINIT 1000000

using namespace std;

FILE * fin = fopen("bellmanford.in", "r");
FILE * fout = fopen("bellmanford.out", "w");

void citire();
bool bellmanford();
void afisare();

int n, m;
queue <int> coada;
int dmin[NMAX], nr[NMAX], pred[NMAX];
vector < pair<int, int> > graf[NMAX];

int main()
{
    citire();
    if (bellmanford() == true)afisare();
    else fprintf(fout, "Ciclu negativ!\n");
    return 0;
}

void citire()
{
    int i, x, y, cost;
    fscanf(fin, "%d %d", &n, &m);
    for (i = 1; i <= m; i ++)
    {
        fscanf(fin, "%d%d%d", &x, &y, &cost);
        graf[x].push_back(make_pair(y, cost));
    }
}

bool bellmanford()
{
    int i, x, y, c;
    for (i = 2; i <= n; i ++)
    {
        pred[i] = 1;
        dmin[i] = INFINIT;
    }
    coada.push(1);
    nr[1]++;
    while (!coada.empty())
    {
        x = coada.front();
        coada.pop();
        for (i = 0; i < graf[x].size(); i ++)
        {
            y = graf[x][i].first;
            c = graf[x][i].second;
            if (dmin[y] > dmin[x] + c)
            {
                dmin[y] = dmin[x] + c;
                pred[y] = x;
                coada.push(y);
                nr[y] ++;
                if (nr[y] == n) return false;
            }
        }
    }
    return true;
}

void afisare()
{
    int i;
    for (i = 2; i <= n; i ++)
        fprintf(fout, "%d ", dmin[i]);
    fprintf(fout, "\n");
}