#include <bits/stdc++.h>
#define INF 1000000008
#define NMAX 108

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

struct Muchie
{
    int vf, c;
};

struct comparare
{
    bool operator() (const Muchie & a, const Muchie & b)
    {
        return a.c > b.c;
    }
};

int n, m, start = 1;
int dmin[NMAX], pre[NMAX];
bool uz[NMAX];
vector <Muchie> G[NMAX];
priority_queue <Muchie, vector<Muchie>, comparare> H;

void Dijkstra();

int main()
{
    int x, y, z;
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        fin >> x >> y >> z;
        G[x].push_back({y, z});
    }
    Dijkstra();
    return 0;
}

void Dijkstra()
{
    int vfmin, minim;
    uz[start] = 1;
    for (int i = 1; i <= n; i++) {pre[i] = start; dmin[i] = INF;}
    pre[start] = 0;
    dmin[start] = 0;
    H.push({start, 0});
    while (!H.empty())
    {
        vfmin = H.top().vf;
        minim = H.top().c;
        H.pop();

        if (minim == INF) break;
        uz[vfmin] = 1;
        for (int j = 0; j < G[vfmin].size(); j++)
            if (!uz[G[vfmin][j].vf] && dmin[G[vfmin][j].vf] > minim + G[vfmin][j].c)
            {
                dmin[G[vfmin][j].vf] = minim + G[vfmin][j].c;
                pre[G[vfmin][j].vf] = vfmin;
                H.push({G[vfmin][j].vf, dmin[G[vfmin][j].vf]});
            }
    }

    for (int i = 2; i <= n; i++)
    {
        if (dmin[i] == INF)
            dmin[i] = 0;
        fout << dmin[i] << ' ';
    }
}