#include <fstream>
#include <queue>
#include <bitset>

using namespace std;
ifstream cin ("dijkstra.in");
ofstream cout ("dijkstra.out");

const int NMAX = 5e4;
const int MMAX = 25e4;
const int INF = 1e9;

struct tip_muchie{
    int indice;
    int cost;
};

struct cmp{
    bool operator()(tip_muchie a, tip_muchie b){
        return a.cost > b.cost;
    }
};


int n, m;
int dist[NMAX + 1];
vector<tip_muchie> muchii[MMAX + 1];

bitset<NMAX + 1> vizitat;

void citire(){
    cin >> n >> m;
    for (int i = 1; i <= m; ++i){
        int a;
        tip_muchie aux;
        cin >> a >> aux.indice >> aux.cost;
        muchii[a].push_back(aux);
    }
}

void init_dijkstra(){
    for (int i = 1; i <= n; ++i){
        dist[i] = INF;
        vizitat[i] = false;
    }
}

void dijkstra(int start){
    init_dijkstra();
    dist[start] = 0;
    priority_queue<tip_muchie, vector<tip_muchie>, cmp> pq;
    tip_muchie aux;
    aux.indice = start;
    aux.cost = 0;
    pq.push(aux);
    while (! pq.empty()){
        int x = pq.top().indice;
        pq.pop();
        if (vizitat[x] == true)
            continue;
        else {
            vizitat[x] = true;
            for (auto vecin : muchii[x]){
                if (! vizitat[vecin.indice] and dist[vecin.indice] > vecin.cost + dist[x]){
                    dist[vecin.indice] = vecin.cost + dist[x];
                    pq.push(vecin);
                }
            }
        }
    }
}

void afisare(){
    for (int i = 2; i <= n; ++i){
        if (! vizitat[i])
            cout << 0;
        else cout << dist[i];
        cout << ' ';
    }
}

int main(){
    citire();
    dijkstra(1);
    afisare();
    return 0;
}