#include <fstream>
#include <iostream>
#include <vector>
#include <set>

#define NMAX 50005
#define INF 10000005

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct Arc
{
    int vf, c;
};

int n, m, x0;
int x, y, c;
vector<Arc> cost[NMAX];
int dmin[NMAX], pre[NMAX];
int minim, vfmin;
int vfcrt, costcrt;
int i, j;

set<pair<int, int>> s;

void afisare(int);

int main()
{
    ///CITIRE
    fin >>n>>m; x0 = 1;
    for (i = 1; i <= m; ++i)
    {
        fin >>x>>y>>c;
        cost[x].push_back({y, c});
    }

    ///ALG. LUI DIJKSTRA
    for (i = 1; i <= n; ++i)
        dmin[i] = INF, pre[i] = x0;
    pre[x0] = 0; dmin[x0] = 0;

    s.insert({x0, 0});
    while (!s.empty())
    {
        vfmin = (*s.begin()).first; minim = (*s.begin()).second;
        s.erase(s.begin());
        for (i = 0; i < cost[vfmin].size(); ++i)
        {
            vfcrt = cost[vfmin][i].vf;
            costcrt = cost[vfmin][i].c;
            if (dmin[vfcrt] > minim + costcrt)
            {
                if (dmin[vfcrt] != INF)
                    s.erase(s.find({vfcrt, dmin[vfcrt]}));
                dmin[vfcrt] = minim + costcrt;
                pre[vfcrt] = vfmin;
                s.insert({vfcrt, dmin[vfcrt]});
            }
        }
    }

    ///AFISARE
    for (i = 2; i <= n; ++i)
        if (dmin[i] == INF) fout <<0<<' ';
        else fout <<dmin[i]<<' ';
    fout <<'\n';

    //afisare(1);
    fout.close();
    return 0;
}

void afisare(int vf)
{
    if (vf == x0)
    {
        fout <<x0<<' ';
        return;
    }

    afisare(pre[vf]);
    fout <<vf<<' ';
}