#include <fstream>
#include <iostream>
#include <set>
#include <vector>
#include <string.h>
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int cost[50005], viz[50005], n, m;

struct vecin
{
    int info, c;
    bool operator< (const vecin& other) const
    {
        if(c == other.c)
            return info < other.info;
        return c < other.c;
    }
};
vector<vecin> nod[50005];
set<vecin> S;

void citire()
{
    f>>n>>m;
    int x, y, c;
    for(int i = 0; i<m; ++i)
    {
        f>>x>>y>>c;
        nod[x].push_back({y, c});
    }
}

bool dijkstra()
{
    S.insert({1, 0});
    while(!S.empty())
    {
        int currNod = S.begin()->info;
        int len = S.begin()->c;
        S.erase(S.begin());

        for(auto p : nod[currNod])
        {
            if(cost[p.info] > cost[currNod] + p.c)
            {
                S.insert({p.info, len+1});
                cost[p.info] = cost[currNod] + p.c;
                viz[p.info] = 1;
            }
        }
    }
    return true;
}

int main()
{
    memset(cost, 11, sizeof(cost));
    cost[1] = 0;
    citire();
    if(dijkstra() == false)
        g<<"Ciclu negativ!";
    else
        for(int i = 2; i<=n; ++i)
        {
            g<<cost[i]<<" ";
        }
    return 0;
}