#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

#define FIN "dijkstra.in"
#define FOUT "dijkstra.out"

#define N 50001
#define INF 100000

int n, m, h[N], p[N], end, d[N];

vector < pair <int, int> > v[N];

void swap(int a, int b, int V[])
{
    int aux;

    aux = V[a];

    V[a] = V[b];

    V[b] = aux;
}

void down_heap(int i, int n)
{
	int j = i;

	if (2 * i <= n && d[h[j]] > d[h[2 * i]])
		j = 2 * i;

    if (2 * i + 1 <= n && d[h[j]] > d[h[2 * i + 1]])
		j = 2 * i + 1;

	if (i != j)
	{
        swap(h[i], h[j], p);
        swap(i, j, h);

		down_heap(j, n);
	}
}

void up_heap(int i, int n)
{
    if (i > 1 && d[h[i]] < d[h[i / 2]])
    {
        swap(h[i], h[i / 2], p);
        swap(i, i / 2, h);

        up_heap(i / 2, n);
    }
}

void solve()
{
    int i, k = 0;

    h[end = 1] = 1;

    for (i = 2; i <= n; ++ i)
        d[i] = INF;

    while (end)
    {
        k = h[1];

        for (i = 0; i < v[k].size(); ++ i)
            if (d[v[k][i].first] >= d[k] + v[k][i].second && p[v[k][i].first] != INF)
            {
                d[v[k][i].first] = d[k] + v[k][i].second;

                if (p[v[k][i].first])
                {
                    up_heap(p[v[k][i].first], end);
                    down_heap(p[v[k][i].first], end);
                }
                else
                {
                    h[++ end] = v[k][i].first;

                    p[v[k][i].first] = end;

                    up_heap(end, end);
                }
            }

        swap(1, end, h);

        -- end;

        down_heap(1, end);

        p[k] = INF;
    }
}

void read()
{
    int i, j, a, b, c;
    char s[30];

    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);

    scanf("%d%d\n", &n, &m);

    for (i = 1; i <= m; ++ i)
    {
        gets(s);

        a = b = c = 0;

        for (j = 0; s[j] != ' '; ++ j)
            a = a * 10 + (s[j] - '0');

        for (++ j; s[j] != ' '; ++ j)
            b = b * 10 + (s[j] - '0');

        for (++ j; s[j] && s[j] != 13; ++ j)
            c = c * 10 + (s[j] - '0');

        v[a].push_back(make_pair(b, c));

        scanf("\n");
    }
}

int main()
{
    int i;

    read();

    solve();

    for (i = 2; i <= n; ++ i)
        if (d[i] != INF)
            printf("%d ", d[i]);
        else
            printf("0 ");

    printf("\n");
}