#include <bits/stdc++.h>

using namespace std;

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

struct nod{
    int ind, c;
};

class Compare {
    public:
       bool operator()(nod a, nod b){
               return a.c < b.c;
      }
};

priority_queue<nod, vector<nod>, Compare> q;

int n, m;

vector<nod> v[250001];
int dist[50001];
int viz[50001];
int main()
{
    in >> n >> m;

    int a, b, c;
    for(int i = 0; i < m; i ++){
        in >> a >> b >> c;
        v[a].push_back({b, c});
    }

    for(int i = 0 ; i <= n; i ++){
        dist[i] = (1<<30);
    }

    q.push({1, 0});
    dist[1] = 0;
    while(!q.empty()){
            // iau current,
        nod current = q.top();
        q.pop();

        if(viz[current.ind])
            continue;
        else{
            for(nod vecin : v[current.ind]){
                if(dist[current.ind] + vecin.c < dist[vecin.ind]){
                    dist[vecin.ind] = dist[current.ind] + vecin.c;
                    q.push({vecin.ind, dist[vecin.ind]});
                }
            }
        }
    }
    for(int i = 2; i <= n; i ++)
        out << dist[i] << " ";
    return 0;
}