#include <fstream>
#include <queue>
#include <vector>
#define N 50005
#define INF 100000
using namespace std;

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

int n, m;
int noduri[N];
bool fol[N];

vector<pair<int, int> > graf[N];

struct comp{

    bool operator()(int x, int y){
        return noduri[x] > noduri[y];
    }
};

priority_queue<int, vector <int>, comp> coada;

void dijkstra(int nod_start){

    for(int i = 1; i <= n; ++i)
        noduri[i] = INF;

    noduri[nod_start] = 0;

    coada.push(nod_start);
    fol[nod_start] = 1;
    while(!coada.empty()){

        int nod = coada.top();
        coada.pop();
        fol[nod] = 0;

        for(int i = 0; i < graf[nod].size(); ++i){
            int vecin = graf[nod][i].first;
            int cost = graf[nod][i].second;

            if(noduri[nod] + cost < noduri[vecin]){
                noduri[vecin] = noduri[nod] + cost;
                if(fol[vecin] == 0) coada.push(vecin), fol[vecin] = 1;
            }
        }
    }
}

int main(){

    in>>n>>m;
    for(int i = 1; i <= m; ++i){
        int x, y, c;
        in>>x>>y>>c;
        graf[x].push_back(make_pair(y,c));
    }

    dijkstra(1);

    for(int i = 2; i <= n; i++)
        if(noduri[i] != INF) out<<noduri[i]<<" ";
        else out<<0<<" ";
    return 0;
}