#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 son;
    do
    {
        son = 0;

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

        if(2*poz <= h[0]  && d[h[2*poz]] < d[h[poz]] && son == 0)
        {
            son = 2*poz;
        }

        if(son)
        {
            swap(h[poz], h[son]);
            poz_heap[h[poz]] = poz;
            poz_heap[h[son]] = son;
            poz = son;
        }

    } while(son);
}

/*
void heap_sift(int poz) {
  int tmp_poz;
  do {
    tmp_poz = poz;
    if (tmp_poz*2 <= h[0] && d[h[poz]] > d[h[tmp_poz*2]]) {
      poz = tmp_poz*2;
    }
    if (tmp_poz*2+1 <= h[0] && d[h[poz]] > d[h[tmp_poz*2+1]]) {
      poz = tmp_poz*2+1;
    }
    swap(h[poz], h[tmp_poz]);
    poz_heap[h[poz]] = poz;
    poz_heap[h[tmp_poz]] = tmp_poz;
  } while (tmp_poz != poz);
}
*/

void heap_percolate(int poz)
{

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

}

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

    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;

    for(int i=1;i<=N && h[0] > 0;++i)
    {
        int c;
        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)
        {
            if(d[it->first] > d[c] + it->second)
            {
                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;


}