#include <fstream>
#include <iostream>
#include <vector>
#define NMAX 50000

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

long long n, m, k, p[NMAX+10], h[NMAX+10];
long long d[NMAX+10];
vector <pair <long long, long long> > a[NMAX+10];

void siftUp(long long x)
{
    long long poz = p[x];
    while(poz > 1 && d[h[poz]] < d[h[poz/2]])
        {   swap(p[h[poz]], p[h[poz/2]]);
            swap(h[poz], h[poz/2]);
            poz /= 2;
        }
}

void siftDown(long long x)
{
    long long tata = p[x], fiu = tata*2;
    while(fiu <= k)
        {   if(fiu < k && d[h[fiu]] > d[h[fiu+1]]) fiu++;
            if(d[h[tata]] > d[h[fiu]])
                {   swap(p[h[tata]], p[h[fiu]]);
                    swap(h[tata], h[fiu]);
                    tata = fiu;
                    fiu = fiu * 2;
                }
            else break;

        }
}

void updateHeap(long long x, long long val)
{
    long long poz = p[x];
    while(poz > 1)
        {   swap(p[h[poz]], p[h[poz/2]]);
            swap(h[poz], h[poz/2]);
            poz /= 2;
        }
    d[h[1]] = val;
    siftDown(h[1]);
}

void addHeap(long long x, long long val)
{
    h[++k] = x;
    d[x] = val;
    p[x] = k;
    siftUp(x);
}

void popHeap()
{
    swap(p[h[1]], p[h[k]]);
    h[1] = h[k];
    k--;
    siftDown(h[1]);

}

int main()
{
    f >> n >> m;
    for(long long i=1; i<=m; i++)
        {   long long nod1, nod2, cost;
            f >> nod1 >> nod2 >> cost;
            a[nod1].push_back(make_pair(nod2, cost));
        }
    addHeap(1, 0);
    while(k)
        {   long long nod = h[1];
            popHeap();
            for(long long j=0; j<a[nod].size(); j++)
                {   long long vec = a[nod][j].first;
                    long long cost = a[nod][j].second;
                    if(!p[vec]) addHeap(vec, d[nod]+cost);
                    else if(d[nod] + cost < d[vec]) updateHeap(vec, d[nod]+cost);
                }
        }
    for(long long i=2; i<=n; i++) g << d[i] << ' ';
    g << '\n';
    return 0;
}