#include <bits/stdc++.h>
#define INF 20001
using namespace std;
int bottom, n, m, i, a, b, c, d[50005];
struct muchie
{
    int val;
    int cost;
}aux, heap[100005];
vector <muchie> v[50005];
void baga_heap(muchie aux, int bottom)
{
    int poz = bottom;
    heap[bottom] = aux;
    while(heap[poz].cost < heap[poz / 2].cost)
    {
        swap(heap[poz], heap[poz / 2]);
        poz = poz / 2;
    }
}
muchie min_heap()
{
    muchie minn = heap[1];
    int poz = 1;
    heap[1] = heap[bottom];
    bottom--;
    while((heap[poz].cost > heap[2 * poz].cost && heap[2 * poz].val != 0) || (heap[poz].cost > heap[2 * poz + 1].cost && heap[2 * poz + 1].val != 0))
    {
        if(heap[poz].cost > heap[2 * poz].cost && heap[2 * poz].val != 0)
        {
            swap(heap[poz], heap[2 * poz]);
            poz = 2 * poz;
        }
        else
        {
            swap(heap[poz], heap[2 * poz + 1]);
            poz = 2 * poz + 1;
        }
    }
    return minn;
}
int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    f >> n >> m;
    for(i = 1; i <= m; i ++)
    {
        f >> a >> b >> c;
        aux.val = b;
        aux.cost = c;
        if(a == 1)
        {
            d[b] = c;
            baga_heap(aux, bottom + 1);
            bottom++;
        }
        else if(b != 1)v[a].push_back(aux);
        aux.val = a;
        aux.cost = c;
        if(b == 1)
        {
            d[a] = c;
            baga_heap(aux, bottom + 1);
            bottom++;
        }
        else if(a != 1)v[b].push_back(aux);
    }
    while(true)
    {
        if(bottom == 0)break;
        muchie poz = min_heap();
        for(i = 0; i < v[poz.val].size(); i ++)
        {
            muchie nod = v[poz.val][i];
            if(nod.val != poz.val && (d[nod.val] > poz.cost + nod.cost || d[nod.val] == 0))
            {
                d[nod.val] = poz.cost + nod.cost;
                aux.val = nod.val;
                aux.cost = d[nod.val];
                baga_heap(aux, bottom + 1);
                bottom++;
            }
        }
    }
    for(i = 2; i <= n; i ++)
        g << d[i] << " ";
    return 0;
}