#include <fstream>
#include <vector>
#define f_mare 8000000005
#include <set>

using namespace std;

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

long long dist[50005],n,m,i,j,x,y,c,l;
vector<long long> ls[50005], lc[50005];
set <pair <long long, int> >dij;
set <pair<long long,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);
    }
    for (i = 2; i <= n; i++)
        dist[i] = f_mare;
    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 (dist[x] + 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] = dist[x] + 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] == f_mare?0:dist[i]) << ' ';
    return 0;
}