#include <iostream>
#include <fstream>
#include <vector>
#include <utility>
#include <set>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n,m,x,y,c;
vector<pair<int,int>> v[50005];
bool viz[50005];
int dist[50005];
int inf = 1000000000;
set<pair<int,int>> s;
int main() {
        fin>>n>>m;
        for (int i = 1;i<=m;++i) {
                fin>>x>>y>>c;
                v[x].emplace_back(y,c);
        }
        dist[1] = 0;
        for (int i=2;i<=n;++i) {
                dist[i] = inf;
        }
        s.insert({0,1});
        while(!s.empty()) {
                int nod = s.begin()->second;
                s.erase(s.begin());
                for (auto el : v[nod]) {
                        if (dist[el.first]>dist[nod]+el.second) {
                                s.erase({dist[el.first],el.first});
                                dist[el.first] = dist[nod]+el.second;
                                s.insert({dist[el.first],el.first});
                        }
                }
        }
        for (int i = 2;i<=n;++i) {
                if (dist[i]==inf) {
                        fout<<0<<' ';
                } else {
                        fout<<dist[i]<<" ";
                }
        }
        return 0;
}