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

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

const int INF = 0x3f3f3f3f;

int cost[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});
    }
    for(int i = 2; i<=n; ++i)
        cost[i] = INF;
}

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

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

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