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

using namespace std;

#define MAXN 50005
#define MAXC 1024

int N, d[MAXN];

vector< pair<int, int> > con[MAXN];
queue<int> Q[MAXC];

#define Q(i) Q[ (i) & 1023 ]

int main()
{
    freopen("dijkstra.in", "rt", stdin);
    freopen("dijkstra.out", "wt", stdout);

    int M;
    scanf("%d %d", &N, &M);
    for (; M; M--)
    {
        int x, y, cst;
        scanf("%d %d %d", &x, &y, &cst);

        con[x].push_back( make_pair(y, cst) );
    }

    memset( d, 0x3f, sizeof(d) );
    d[1] = 0; Q(0).push(1);

    int left = 1;
    for (int CST = 0; left; CST++)
        for (; !Q(CST).empty(); Q(CST).pop())
        {
            int i = Q(CST).front();
            left--;

            if (d[i] != CST)
                continue;

            vector< pair<int, int> > :: iterator it;
            for (it = con[i].begin(); it != con[i].end(); it++)
                if (d[i] + (*it).second < d[(*it).first])
                {
                    d[ (*it).first ] = d[i] + (*it).second;
                    Q( d[ (*it).first ] ).push( (*it).first );
                    left++;
                }
        }

    for (int i = 2; i <= N; i++)
        if (d[i] == 0x3f3f3f3f)
            printf("0 ");
        else
            printf("%d ", d[i]);
    printf("\n");

    return 0;
}