#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>

#define INF 99999999
#define MAXN 500000+10

using namespace std;

struct data {
    int nod, dist;
}dt;

FILE *f, *g;
int n, m, x;
int d[MAXN];
vector <data> v[MAXN];
queue <data> q;

void ReadInputData ()
{
    fscanf(f, "%d %d", &n, &m);

    for (int i = 1; i <= m; i++)
        fscanf(f, "%d %d %d", &x, &dt.nod, &dt.dist),
        v[x].push_back(dt);

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

void Dijkstra (int sNode)
{
    dt.nod=sNode; dt.dist=0; d[sNode]=0;
    q.push(dt);

    while(!q.empty())
    {
        int k = q.front().nod;
        for (int 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();
    }
    for (int i = 2; i <= n; i++)
        fprintf(g, "%d ", d[i] != INF ? d[i] : 0);
}

int main()
{
    f = fopen("dijkstra.in", "r");
    g = fopen("dijkstra.out", "w");

    ReadInputData();
    Dijkstra(1);

    fclose(f);
    fclose(g);

    return 0;
}