#include <fstream>
#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;

class compare
{
public:
    bool operator () (const int& x, const int& y)
    {
        return dmin[x] > dmin[y];
    }
};

set<int, compare> 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);
    while (!s.empty())
    {
        vfmin = *s.begin(); s.erase(s.begin());
        minim = dmin[vfmin];
        for (i = 0; i < cost[vfmin].size(); ++i)
        {
            vfcrt = cost[vfmin][i].vf;
            costcrt = cost[vfmin][i].c;
            if (dmin[vfcrt] > minim + costcrt)
            {
                if (s.find(vfcrt) != s.end())
                    s.erase(s.find(vfcrt));
                dmin[vfcrt] = minim + costcrt;
                pre[vfcrt] = vfmin;
                s.insert(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<<' ';
}