#include <cstdio>
#include <vector>
#include <algorithm>
#define oo 0x7fffffff
using namespace std;

int dist[50001];

struct distante
{
    int d, i;
    bool operator<(const distante &a) const
    {
        return d > a.d;
    }
} h[50001];

int n, m, len;
vector<pair<int, int> > adj[50001];
bool viz[50001];

void dijkstra()
{
    for (int i = 2; i <= n; i++)
        dist[i] = oo;

    h[0].i = 1;
    h[0].d = 0;
    len = 1;
    while (len)
    {
        int nod = h[0].i, d = h[0].d;

        pop_heap(h, h + len);
        len--;

        if (!viz[nod])
        {
            viz[nod] = 1;
            dist[nod] = d;
            for (int i = 0; i < adj[nod].size(); i++)
            {
                int next = adj[nod][i].first, c = d + adj[nod][i].second;
                if (c < dist[next])
                {
                    h[len].i = next;
                    h[len++].d = c;
                    push_heap(h, h + len);
                    dist[next] = c;
                }
            }
        }
    }
}

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

    int x, y, c;

    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++)
    {
        scanf("%d %d %d", &x, &y, &c);
        adj[x].push_back(make_pair(y, c));
    }

    dijkstra();
    for (int i = 2; i <= n; i++)
        if (dist[i] != oo)
            printf("%d ", dist[i]);
        else
            printf("0 ");
}