#include <cstdio>
#include <vector>
#include <queue>
#define inf 1 << 30
#define add push_back
#define nmax 50000+5
using namespace std;

struct muchie
{
    int destinatie;
    int cost;

    muchie(int d = 0, int c = 0): destinatie(d), cost(c)
    {

    }
};

vector<muchie> graf[nmax];
int pas[nmax];
bool eInCoada[nmax];
int nrVizitari[nmax];

struct cmp
{
    bool operator()(const int & a, const int & b)
    {
        return pas[a] > pas[b];
    }
};

queue<int> coada;
int n, m;

void bellmanford()
{
    int curent, vecin;
    int k, pasTentativ;

    for (k = 1; k <= n; k++)
    {
        pas[k] = inf;
        nrVizitari[k] = 0;
        eInCoada[k] = 0;
    }

    pas[1] = 0;
    nrVizitari[1] = 1;
    eInCoada[1] = 1;
    coada.push(1);



    while (!coada.empty())
    {
        curent = coada.front();
        coada.pop();

        for (k = 0; k < graf[curent].size(); k++)
        {
            vecin = graf[curent][k].destinatie;
            if ((pasTentativ = pas[curent] + graf[curent][k].cost) < pas[vecin])
            {
                pas[vecin] = pasTentativ;

                nrVizitari[vecin]++;
                if (nrVizitari[vecin] > n)
                {
                    printf("Ciclu negativ!");
                    return;
                }
                if (!eInCoada[vecin])
                    coada.push(vecin);
            }


        }

        eInCoada[curent] = 0;
    }

    for (k = 2; k <= n; k++)
        printf("%d ", pas[k]);
}

int main()
{
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);

    int index;
    int a, b, c;
    scanf("%d%d", &n, &m);

    for (index = 1; index <= m; index++)
    {
        scanf("%d%d%d", &a, &b, &c);
        graf[a].add(muchie(b, c));
    }

    bellmanford();
    return 0;
}