#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

const int NMAX = 50010, INF = 0x3f3f3f3f;

int N, M, A, B, C, Dist[NMAX];
vector<pair<int, int> > G[NMAX];
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > Q;

void Dijkstra()
{
    for(int i = 1; i <= N; ++ i) Dist[i] = INF;
    Dist[1] = 0;
    Q.push(make_pair(0, 1));

    while(!Q.empty())
    {
        int Node = Q.top().second;
        Q.pop();

        for(vector<pair<int, int> > :: iterator it = G[Node].begin(); it != G[Node].end(); ++ it)
            if(Dist[it -> first] > Dist[Node] + it -> second)
            {
                Dist[it -> first] = Dist[Node] + it -> second;
                Q.push(make_pair(Dist[it -> first], it -> first));
            }
    }

    for(int i = 2; i <= N; ++ i)
        printf("%i ", (Dist[i] == INF ? 0 : Dist[i]));
}

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

    scanf("%i %i", &N, &M);
    for(int i = 1; i <= M; ++ i)
    {
        scanf("%i %i %i", &A, &B, &C);
        G[A].push_back(make_pair(B, C));
    }

    Dijkstra();
}