/// Probema "Dijkstra" - InfoArena
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>

#define in "dijkstra.in"
#define out "dijkstra.out"
#define NMAX (50000 + 7)
#define pb push_back
#define inf (1000000000 + 7)

using namespace std;
int N, M, aux, d[NMAX];
struct muchie
{
    int Nod;
    int Cost;
    bool operator <(const muchie &aux) const
    {
        return (Cost > aux.Cost);
    }
} tmp;
vector <muchie> adj[NMAX];
priority_queue <muchie> H;

inline void dijkstra(const int &Node)
{
    for(int i = 1; i<= N; ++i) d[i] = inf;
    d[Node] = 0;
    H.push({Node, 0});
    while(!H.empty())
    {
        int nod = H.top().Nod, cost = H.top().Cost;
        H.pop();
        if(cost > d[nod]) continue;
        int sze = adj[nod].size();
        for(int i = 0; i< sze; ++i)
        {
            if(d[nod] + adj[nod][i].Cost < d[adj[nod][i].Nod])
            {
                d[adj[nod][i].Nod] = d[nod] + adj[nod][i].Cost;
                H.push({adj[nod][i].Nod, d[adj[nod][i].Nod]});
            }
        }
    }
}

int main()
{
    freopen(in, "r", stdin);
    freopen(out, "w", stdout);
    scanf("%d %d", &N, &M);
    for(; M; --M)
    {
        scanf("%d %d %d", &aux, &tmp.Nod, &tmp.Cost);
        adj[aux].pb(tmp);
    }
    dijkstra(1);
    for(int i = 2; i<= N; ++i) printf("%d ", (d[i]==inf)?0:d[i]);
    printf("\n");
    return 0;
}