#include <cstdio>
#include <vector>
#include <queue>

#define Nmax 50005
#define INF 0x3f3f3f3f / 2

using namespace std;

int N, M, Cost[Nmax];
vector <pair <int, int> > A[Nmax];
priority_queue <pair <int, int>, vector <pair <int, int> >, greater <pair <int, int> > > Q;

void Citire()
{
    int a, b, c;
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= M; ++i)
    {
        scanf("%d %d %d", &a, &b, &c);
        A[a].push_back(make_pair(b, c));
    }
    for (int i = 2; i <= N; ++i)
        Cost[i] = INF;
}

void Dijkstra()
{
    int nodcrt;
    vector <pair <int, int > > :: iterator i;
    Q.push(make_pair(1, 0));
    while (!Q.empty())
    {
        nodcrt = Q.top().first;
        Q.pop();
        for (i = A[nodcrt].begin(); i != A[nodcrt].end(); ++i)
        {
            if (Cost[i -> first] > Cost[nodcrt] + i -> second)
            {
                Cost[i -> first] = Cost[nodcrt] + i -> second;
                Q.push(make_pair(i -> first, Cost[i -> first]));
            }
        }
    }
}

void Afisare()
{
    for (int i = 2; i <= N; ++i)
        if (Cost[i] == INF)
            printf("0 ");
        else
            printf("%d ", Cost[i]);
}

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    Citire();
    Dijkstra();
    Afisare();

    return 0;
}