#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<utility>

using namespace std;

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

vector<pair<int, int> > H;
int n, m, startVertex, C[100][100], D[100];

// Functie de citire
void readIn() {
    int i,j
    f>>n>>m;
    for(int k=1;k<=m;k++) {

        f>>i>>j>>C[i][j];
    }
    f.close();
    for(int i=1;i<=n;i++) {
        H.push_back(make_pair(C[startVertex][i], i));
    }
    make_heap(H.begin(), H.end());
    D[startVertex]=H.at(n-1).first;
    H.pop_back();
    sort_heap(H.begin(), H.end());
}// END OF readIn FUNCTION

// Algoritmul lui Dijkstra Optimizat
void dijkstra() {
    int i,j,k, minPos, minLen;
    for(i=1;i<=n-1;i++) {

        minLen=H.at(0).first;
        minPos=H.at(0).second;
        D[minPos]=minLen;
        pop_heap(H.begin(), H.end());
        H.pop_back();
        sort_heap(H.begin(), H.end());
        for(k=0;k<H.size();k++)
            if(H.at(k).first>minLen+C[minPos][H.at(k).second])
                H.at(k).first=minLen+C[minPos][H.at(k).second];
    }
}// END OF dijkstra FUNCTION */

int main() {

    readIn();
    dijkstra();
    for(int i=2;i<=n;i++) g<<D[i]<<" ";
    g.close();
    return 0;
}// END OF main FUNCTION