#include <cstdio>
#include <vector>
#include <queue>
#define MAX 50005
#define INF (1 << 30)

using namespace std;

struct data{
    int nod, dist;
}dt;

int n, m, x, d[MAX];
vector<data> v[MAX];
queue<data> q;

void read();
void solve(int node);
void write();

int main()
{
    read();
    solve(1);
    write();
    return 0;
}

void read()
{
    freopen ("dijkstra.in", "r", stdin);
    scanf ("%d%d", &n, &m);
    for(int i = 1; i <= m; ++i)
        scanf ("%d %d %d", &x, &dt.nod, &dt.dist),
        v[x].push_back(dt);

    for (int i = 1; i <= n; ++i)
        d[i] = INF;
    fclose(stdout);
}

void solve(int node)
{
    dt.nod = node, dt.dist = 0, d[node] = 0;
    q.push(dt);

    while(!q.empty())
    {
        int k = q.front().nod;
        for (unsigned i = 0; i < v[k].size(); ++i)
            if (d[v[k][i].nod] > d[k] + v[k][i].dist)
                d[v[k][i].nod] = d[k] + v[k][i].dist,
                q.push(v[k][i]);
        q.pop();
    }
}

void write()
{
    freopen ("dijkstra.out", "w", stdout);
    for (int i = 2; i <= n; ++i)
        printf ("%d ", d[i] == INF ? 0 : d[i]);
    printf ("\n");
    fclose(stdout);
}