#include<fstream>
#include<vector>
using namespace std;
int n, i, j, m, x, y, vecin, nod, cost, z;
int d[50005], viz[50005];
vector< pair<int, int> > v[50005];
pair<int, int> p;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int main(){
    fin>> n >> m;
    for(i = 1; i <= m; i++){
        fin>> x >> y >> z;
        p.first = y;
        p.second = z;
        v[x].push_back(p);
    }
    for(i = 2; i <= n; i++){
        d[i] = 1000000000;
    }
    d[0] = 1000000000;
    for(i = 1; i <= n; i++){
        nod = 0;
        for(j = 1; j <= n; j++){
            if(d[j] < d[nod] && viz[j] == 0){
                nod = j;
            }
        }
        viz[nod] = 1;
        for(j = 0; j < v[nod].size(); j++){
            vecin = v[nod][j].first;
            cost = v[nod][j].second;
            if(d[vecin] > d[nod] + cost && viz[vecin] == 0){
                d[vecin] = d[nod] + cost;
            }
        }
    }
    for(i = 2; i <= n; i++){
        fout<< d[i] <<" ";
    }
    return 0;
}