#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
const int nmax = 50000;

int h[nmax + 1], u[nmax +1], c[nmax + 1];
int h_size;
bool viz[nmax + 1];

vector <pair<int, int> > g[nmax + 1];


void heap_swap(int a, int b)
{
    swap(u[h[a]], u[h[b]]);
    swap(h[a], h[b]);

}
void heap_up(int p)
{
    int up = p / 2;
    while(c[h[p]] < c[h[up]]) {
        heap_swap(p, up);
        p = p / 2;
        up = up / 2;
    }
}
void heap_down(int p)
{
    int l, r, best;
    while(2 * p <= h_size) {
        l = 2 * p;
        best = l;
        r = 2 * p + 1;
        if(r <= h_size && c[h[r]] < c[h[l]]) {
            best = r;
        }
        if(c[h[p]] > c[h[best]]) {
            heap_swap(p, best);
        } else {
            break;
        }
        p = best;
    }
}
void heap_insert(int x)
{
    ++h_size;
    h[h_size] = x;
    u[x] = h_size;
    heap_up(h_size);
}
void heap_update(int x)
{
    int p = u[x];
    heap_up(p);
}
void heap_erase(int x)
{
    int p = u[x];
    heap_swap(p, h_size);
    --h_size;
    heap_up(p);
    heap_down(p);

}
void dijkstra()
{
    int x;

    viz[1] = 1;
    c[1] = 0;
    heap_insert(1);

    while(h_size > 0)
    {
        x = h[1];
        heap_erase(x);

        for(int i = 0; i < g[x].size(); ++i) {
            if(viz[g[x][i].first] == 0) {
                viz[g[x][i].first] = 1;
                c[g[x][i].first] = c[x] + g[x][i].second;
                heap_insert(g[x][i].first);
            }else if(c[x] + g[x][i].second < c[g[x][i].first]) {
                c[g[x][i].first] = c[x] + g[x][i].second;
                heap_update(g[x][i].first);
            }
        }
    }
}


int main()
{
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");

    int n, m, x, y, z;
    fin >> n >> m;
    for(int i = 1; i <= m; ++i) {
        fin >> x >> y >> z;
        g[x].push_back(make_pair(y, z));
    }
    dijkstra();
    for(int i = 2; i <= n; ++i) {
        fout << c[i] << " ";
    }
    return 0;
}