#include <fstream>
#include <vector>
#include <set>

using namespace std;

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

int dist[50005],n,m,i,j,x,y,c,l;
vector<int> ls[50005], lc[50005];
set <pair <int, int> >dij;
set <pair<int,int> >::iterator w;

int main() {
    f >> n >> m;
    for (i = 1; i <= m; i++) {
        f >> x >> y >> c;
        ls[x].push_back(y);
        lc[x].push_back(c);
        ls[y].push_back(x);
        lc[y].push_back(c);
    }
    for (i = 2; i <= n; i++)
        dist[i] = 1000000005;
    dij.insert(make_pair(0,1));
    while (dij.empty() == 0) {
        x = dij.begin() ->second;
        c = dij.begin() ->first;
        dij.erase(dij.begin());
        l = ls[x].size();
        for (i = 0; i < l; i++) {
            y = ls[x][i];
            if (c + lc[x][i] < dist[y]) {
                w = dij.find(make_pair(dist[y], y)); // scoate costul vechi al nodului y
                if (w != dij.end())
                    dij.erase(w);
                dist[y] = c + lc[x][i];              // dupa ce actualizeaza costul,
                dij.insert(make_pair(dist[y], y));   // pune costul nou in set
            }
        }
    }
    for (i = 2; i <= n; i++)
        g << dist[i] << ' ';
    return 0;
}