#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<climits>
#include<set>
using namespace std;

vector<vector<pair<int, int>>> List;
ifstream f("dijkstra.in");
ofstream out("dijkstra.out");

vector<int> getChain(vector<int> t, int a)
{
    vector<int>chain;
    while(a){
        chain.push_back(a);
        a = t[a];}
    return chain;
}


vector<int> dijkstra(int a, vector<int> &t)
{
    t[a] = 0;
    priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;
    pq.push({0, a});
    vector<int> vis(List.size()+1, 0), d(List.size() + 1, INT_MAX);
    d[a] = 0;

    while(!pq.empty()){
        vector<int> c = pq.top();
        pq.pop();
        int current_node = c[1];
        int current_cost = c[0];

        if(!vis[current_node]){
            vis[current_node] = 1;
            d[current_node] = current_cost;
        }

        for(auto x : List[current_node]){
            if(!vis[x.second] && d[x.second] > d[current_node] + x.first){
                pq.push({d[current_node] + x.first, x.second});
                d[x.second] = d[current_node] + x.first;
                t[x.second] = current_node;
            }
        }
    }
    return d;

}

int main()
{

    int n, m, a, b, c, x, y, z;
    f>>n>>m;

    for(int i=0; i<=n; i++)
        List.push_back({});

   // f>>a>>b>>c;

    for(int i=0; i<m; i++){
        f>>x>>y>>z;

        List[x].push_back(make_pair(z, y));

    }

    vector<int> ta(n+1, 0), da;
   da = dijkstra(1, ta);
   for(int i=1; i<=n; i++)
    if(da[i] == INT_MAX) da[i] = 0;


   for(int i=2; i<=n; i++) out<<da[i]<<" ";

    return 0;
}