#include <bits/stdc++.h>
#define MAX 50002
#define INF (1 << 20)
#define pii pair< int, int >
#define pb(x) push_back(x)
FILE *fin  = freopen("dijkstra.in", "r", stdin);
FILE *fout = freopen("dijkstra.out", "w", stdout);

using namespace std;
int V, E, starting;
struct comp
{
    bool operator() (const pii &a, const pii &b)
    {
        return a.second > b.second;
    }
};
priority_queue< pii, vector< pii >, comp > Q;
vector< pii > G[MAX];
int D[MAX];
bool F[MAX];
void read()
{
    int i, u, v, w;
    // create graph
    scanf("%d %d", &V, &E);
    for(i = 1; i <= E; ++ i)
    {
        scanf("%d %d %d", &u, &v, &w);
        G[u].pb(pii(v, w));
        //G[v].pb(pii(u, w)); for undirected
    }
    starting = 1;
    // initialize distance vector
    for(i = 1; i <= V; ++ i) D[i] = INF;
    D[starting] = 0;
    Q.push(pii(starting, 0));
}
void dijkstra()
{
    int u, v, w;
    while(!Q.empty())
    {
        u = Q.top().first;
        Q.pop();

        if(F[u]) continue;
        int sz = G[u].size();
        for(int i = 0; i < sz; ++ i)
        {
            v = G[u][i].first;
            w = G[u][i].second;
            if(!F[v] && D[u] + w < D[v])
            {
                D[v] = D[u] + w;
                Q.push(pii(v, D[v]));
            }
        }
        F[u] = 1; // done with u
    }
}
void write()
{
    for(int i = 2; i <= V; ++ i)
        printf("%d ", D[i]);
}
int main()
{
    read();
    dijkstra();
    write();
    return 0;
}