#include <bits/stdc++.h>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
typedef long long ll;
const int NMAX = 100005;
const ll INF = 2e9+9;
int n, p;

struct muchie
{
    int dest;
    ll dist;
    muchie(int _dest, ll _dist)
    {
        dest = _dest;
        dist = _dist;
    }
};

vector <muchie> g[NMAX];
//min heap
struct heap
{
    int poz;
    ll val;
}h[NMAX];
int position[NMAX], nrel;
ll dist[NMAX];
int root()
{
    return h[1].val;
}

int father(int poz)
{
    return poz / 2;
}

int left_son(int poz)
{
    return 2 * poz;
}

int right_son(int poz)
{
    return 2 * poz + 1;
}

///in jos
void sift(int poz)
{
    int min_son;

    do
    {
        min_son = 0;
        if(left_son(poz) <= nrel)
        {
            min_son = left_son(poz);
            if(right_son(poz) <= nrel && h[right_son(poz)].val < h[min_son].val)
                min_son = right_son(poz);
        }

        if(min_son == 0)
            break;
        if(h[min_son].val > h[poz].val)
            min_son = 0;
        else swap(h[min_son], h[poz]), swap(position[h[min_son].poz], position[h[poz].poz]), poz = min_son;
    }while(min_son != 0);
}

///in sus
void percolate(int poz)
{
    while(poz > 1 && h[father(poz)].val > h[poz].val) swap(h[father(poz)], h[poz]), swap(position[h[father(poz)].poz], position[h[poz].poz]), poz = father(poz);
}

void create()
{
    int i;
    for(i = nrel / 2; i >= 1; --i)
        sift(i);
}

void del(int poz)
{
    if(poz == nrel)
    {
        --nrel;
        return ;
    }

    swap(h[poz], h[nrel]);
    swap(position[h[poz].poz], position[h[nrel].poz]);
    --nrel;

    sift(poz);
    //percolate(poz);
}

void marchez_vecini(int poz_in_heap)
{
    int nrnod = h[poz_in_heap].poz, i;

    for(i = 0; i < g[nrnod].size(); ++i)
    {
        if(dist[g[nrnod][i].dest] != 2 * INF)
            continue ;

        int poz_dest_heap = position[g[nrnod][i].dest];
        h[poz_dest_heap].val = min(h[poz_dest_heap].val, h[poz_in_heap].val + g[nrnod][i].dist);

        percolate(poz_dest_heap);
    }
}

void dij()
{
    dist[p] = 0;
    h[p].val = 0;
    create();

    while(nrel > 0 && h[1].val != INF)
    {
        marchez_vecini(1);
        dist[h[1].poz] = h[1].val;
        del(1);
    }
}
int main()
{
    p = 1;
    int m;
    fin >> n >> m;

    int a, b, f, i;

    for(i = 1; i <= m; ++i)
    {
        fin >> a >> b >> f;
        g[a].push_back(muchie(b, f));
        //g[b].push_back(muchie(a, f));
    }

//    while(fin >> a >> b >> f)
//        g[a].push_back(muchie(b, f));

//    int i, j;
//    for(i = 1; i <= n; ++i)
//    {
//        for(j = 0; j < g[i].size(); ++j)
//            fout << i << ' ' << g[i][j].dest << ' ' << g[i][j].dist << '\n';
//    }

    for(i = 1; i <= n; ++i)
        position[i] = i, dist[i] = 2 * INF, h[i].val = INF, h[i].poz = i;
    nrel = n;
    dij();

    for(i = 2; i <= n; ++i)
        if(dist[i] != 2 * INF)
            fout << dist[i] << ' ';
        else fout << "0 ";
    return 0;
}