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

#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, len, d[NMAX], aux;
struct muchie
{
    int Nod;
    int Cost;
} tmp;
muchie H[NMAX];
vector <muchie> adj[NMAX];

inline void swapp(muchie &a, muchie &b)
{
    muchie tmp;
    tmp = a;
    a = b;
    b = tmp;
}

inline void upheap(const int &key)
{
    int pt = key;
    while(pt > 1)
    {
        if(H[pt].Cost >= H[(pt>>1)].Cost) break;
        swapp(H[pt], H[(pt>>1)]);
        pt >>= 1;
    }
}
inline void downheap(const int &key)
{
    int pt = key;
    while(((pt<<1)|1) <= len)
    {
        if(H[pt].Cost <= min(H[(pt<<1)].Cost, H[((pt<<1)|1)].Cost)) break;
        if(H[(pt<<1)].Cost < H[((pt<<1)|1)].Cost) {swapp(H[pt], H[(pt<<1)]); pt = (pt<<1);continue;}
        if(H[(pt<<1)].Cost >= H[((pt<<1)|1)].Cost) {swapp(H[pt], H[((pt<<1)|1)]); pt = ((pt<<1)|1);continue;}
    }
    if((pt<<1) == len)
    {
        if(H[(pt<<1)].Cost < H[pt].Cost) swapp(H[pt], H[(pt<<1)]);
    }
}
inline void Insert(const int &nod, const int &cost)
{
    H[++len] = {nod, cost};
    upheap(len);
}
inline void elimin()
{
    H[1] = H[len];
    --len;
    downheap(1);
}

inline void dijkstra(const int &node)
{
    for(int i = 1; i<= N; ++i) d[i] = inf;
    d[node] = 0;
    Insert(node, 0);
    while(len)
    {
        int nod = H[1].Nod, cost = H[1].Cost;
        elimin();
        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;
                Insert(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)
    {
        if(d[i] != inf) printf("%d ", d[i]);
        else printf("0 ");
    }
    printf("\n");
    return 0;
}