#include <bits/stdc++.h>
using namespace std;

vector<pair<int,int>> adj[50001];
int viz[50001];
int d[50001];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;

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

int main() {

    int n,m;
    fin>>n>>m;

    for (int i=1;i<=n;i++) {
        viz[i]=0;
        d[i]=INT_MAX;
    }

    int a,b,c;
    for (int i=1;i<=m;i++) {
        fin>>a>>b>>c;
        adj[a].push_back({b,c});
    }


    pq.push({0,1});
    d[1]=0;

    while (pq.size()>0) {
        pair<int,int> curent=pq.top();
        pq.pop();

        if (curent.first!=d[curent.second]) continue;


        for (auto [vecin,pondere]:adj[curent.second]) {
            if (d[vecin]>d[curent.second]+pondere) {
                d[vecin]=d[curent.second]+pondere;
                pq.push({d[vecin],vecin});
            }
        }
    }

    for (int i=2;i<=n;i++) {
        if (d[i]!=INT_MAX) fout<<d[i]<<' ';
        else fout<<0<<' ';
    }


}