/* Algoritmul lui Dijkstra folosind Heapuri */
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define MAX 50001
#define INF 0x3f3f3f3f

vector<pair<int, int> > Edge[MAX];
int Pos[MAX], N, M, X, Y, Z, K, D[MAX], H[MAX];

int Pop()
{
    int Top = H[1], t, f;
    swap(Pos[H[1]], Pos[H[K]]);
    swap(H[1], H[K--]);
    t = 1; f = 2;
    if (f + 1 <= K && D[H[f + 1]] < D[H[f]]) f++;
    while (f <= K && D[H[t]] > D[H[f]])
    {
        swap(Pos[H[t]], Pos[H[f]]);
        swap(H[t], H[f]);
        t = f;
        f = 2 * t;
        if (f + 1 <= K && D[H[f + 1]] < D[H[f]]) f++;
    }
    return Top;
}

void Push(int X)
{
    int t, f;
    if (Pos[X] == 0)
    {
        Pos[X] = ++K;
        H[K] = X;
    }
    f = Pos[X];
    t = f / 2;
    while (t > 0 && D[H[t]] > D[H[f]])
    {
        swap(Pos[H[t]], Pos[H[f]]);
        swap(H[t], H[f]);
        t = f;
        f = t / 2;
    }
}

void Dijkstra()
{
    H[K = 1] = 1;
    for (int i = 2; i <= N; i++) D[i] = INF;
    while (K > 0)
    {
        X = Pop();
        for (int i = 0; i < Edge[X].size(); i++)
        {
            Y = Edge[X][i].first;
            Z = Edge[X][i].second;
            if (D[Y] > D[X] + Z)
            {
                D[Y] = D[X] + Z;
                Push(Y);
            }
        }
    }
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d %d", &N, &M);
    for (int i = 0; i < M; i++)
    {
        scanf("%d %d %d", &X, &Y, &Z);
        Edge[X].push_back(make_pair(Y, Z));
    }
    Dijkstra();
    for (int i = 2; i <= N; i++)
    {
        printf("%d ", D[i] == INF ? 0 : D[i]);
    }
}