#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define NMAX 100100
#define MMAx 250200
#define INF 1000000
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
vector <pair<int,int> > graf[NMAX];
int viz[NMAX];
int cost[NMAX];
int frecventa[NMAX];
int n,m;
struct compara
{
    bool operator()(int x, int y)
    {
        return cost[x] > cost[y];
    }
};
priority_queue<int, vector<int>, compara> coada;
int dijkstra (int nodStart)
{
    cost[nodStart] = 0;
    coada.push(nodStart);
    viz[nodStart] = 1;
    while(!coada.empty())
    {
        int nodCurent = coada.top();
        coada.pop();
        viz[nodCurent] = 0;
        frecventa[nodCurent]++;
        if(frecventa[nodCurent] > m)
        {
            g<<"Ciclu negativ!\n";
            return 0;
        }
        int lim = graf[nodCurent].size();
        for(int i=0; i<lim; i++)
        {
            int vecin = graf[nodCurent][i].first;
            int cos = graf[nodCurent][i].second;
            if(cost[nodCurent] + cos < cost[vecin])
            {
                cost[vecin] = cost[nodCurent] + cos;
                if(viz[vecin] == 0)
                {
                    coada.push(vecin);
                    viz[vecin] = 1;
                }
            }
        }
    }
    return 1;
}
int main()
{
    int x,y,c,i;
    f>>n>>m;
    for(i=1; i<=m; i++)
    {
        f>>x>>y>>c;
        graf[x].push_back(make_pair(y,c));
    }
    for(i=1; i<=n; i++)
    {
        viz[i] = 0;
        cost[i] = INF;
    }
    if(dijkstra(1))
        for(i=2; i<=n; i++) g<<cost[i]<<" ";
    return 0;
}