#include <cstdio>
#include <vector>

#define NMAX 50001
#define INF 50000001
using namespace std;

typedef vector<pair<int, int> > list;

vector<list> v(NMAX);
int h[NMAX]; //in heap tin nodurile nevizitate inca si a caror distanta in d nu e infinit
int d[NMAX], poz_heap[NMAX]; //pozitia pe care se gaseste nodul i in heap

int N, M;

void heap_sift(int poz)
{
    int current = poz, son;

    do
    {
        son = 0;

        if(2*poz <= h[0])
        {
            if(2*poz+1 <= h[0] && d[h[2*poz+1]] < d[h[2*poz]])
            {
                son = 2*poz+1;
            }
            else
            {
                if(d[h[2*poz]] < d[h[poz]])
                {
                    son = 2*poz;
                }
            }
        }
        if(son)
        {
            swap(h[poz], h[2*poz]);
            poz_heap[poz] = 2*poz;
            poz_heap[2*poz] = poz;
            poz = son;
        }

    } while(son);
}

void heap_percolate(int poz)
{
    while(poz > 1 && d[h[poz]] < d[h[poz/2]])
    {
        swap(h[poz], h[poz/2]);
        poz_heap[poz] = poz/2;
        poz_heap[poz/2] = poz;
        poz = poz/2;
    }
}

int heap_get_min()
{
    int m = h[1];
    h[1] = h[h[0]--];

    poz_heap[m] = -1;

    heap_sift(1);

    return m;
}

void heap_add(int val)
{
    h[++h[0]] = val;

    poz_heap[val] = h[0];

    heap_percolate(h[0]);
}

void dijkstra()
{
    for(int i=1;i<=N;++i)
    {
        d[i] = INF;
        poz_heap[i] = -1;
    }

    heap_add(1);
    d[1] = 0;

    while(h[0] > 0)
    {
        int c, t1, t2;
        c = heap_get_min(); //extrag minimul si il si sterg pentru ca l-am vizitat

        for(list::iterator it=v[c].begin();it!=v[c].end();++it)
        {
            t1 = it->first;
            t2 = it->second;
            if(d[it->first] > d[c] + it->second)
            {
                if(d[it->first] == INF)
                {
                    if(poz_heap[it->first] == -1);
                        heap_add(it->first);
                }
                d[it->first] = d[c] + it->second;
                heap_percolate(poz_heap[it->first]);
            }
        }
    }
}

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

    scanf("%d %d", &N, &M);

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

    dijkstra();

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

    h[0] = 0;


}