#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int inf = 1e9;
bool used[50001];
int graf[50001];
int distante[50001];
struct vecin{
    int nod, cost;
};
vector<vecin> vecini[50001];
struct nod_dijk{
    int nod, cost_total;
    bool operator < (nod_dijk other) const{
        return cost_total >= other.cost_total;
    }
};
priority_queue<nod_dijk> q;
void dijkstra(){
    q.push({1, 0});
    distante[0] = 0;
    while (!q.empty()){
        nod_dijk front = q.top();
        q.pop();
        if (used[front.nod]){
            continue;
        }
        used[front.nod] = true;
        for (int i = 0; i < vecini[front.nod].size(); i++){
            nod_dijk next_node;
            next_node.nod = vecini[front.nod][i].nod;
            next_node.cost_total = front.cost_total + vecini[front.nod][i].cost;
            if (next_node.cost_total < distante[next_node.nod]){
                distante[next_node.nod] = next_node.cost_total;
                q.push(next_node);
            }
        }
    }
}
int main(){
    int noduri, muchii;
    fin >> noduri >> muchii;
    for (int i = 1; i <= noduri; i++){
        distante[i] = inf;
    }
    for (int i = 1; i <= muchii; i++){
        int x, y, cost;
        fin >> x >> y >> cost;
        vecini[x].push_back({y, cost});
    }
    dijkstra();
    for (int i = 2; i <= noduri; i++){
        if (distante[i] == inf)
            fout << 0 << " ";
        else
            fout << distante[i] << " ";
    }
    return 0;
}