#include <fstream>
#include <queue>
#include <vector>
using namespace std;
struct code {
    int node , cost;
    bool operator > (code r) const {
        return cost > r . cost;
    }
};
ifstream cin ("dijkstra.in");
ofstream cout ("dijkstra.out");
int const NM = 25e4;
vector <code> v [1 + NM];
int dp [1 + NM];
bool viz [1 + NM];
priority_queue <code , vector <code> , greater <code> > q;
void shortest (){
    q . push ({1 , 0});
    while (! q . empty ()){
        code x = q . top ();
        viz [x . node] = true;
        while (q . size () && viz [q . top () . node])
            q . pop ();
        for(auto i : v [x . node]){
            if (dp [i . node] > dp [x . node] + i . cost ){
                dp [i . node] = dp [x . node] + i . cost;
                q . push ({i . node , dp [i . node]});
            }
        }
    }
}
int main()
{
    int n , m;
    cin >> n >> m ;
    for(int i = 1 ; i <= m ; ++ i){
        int a , b , c;
        cin >> a >> b >> c;
        v [a] . push_back ({b , c});
    }
    fill (dp + 2 , dp + n + 1 , (1 << 30));
    shortest ();
    for(int i = 2 ; i <= n ; ++ i)
        if (dp [i] == (1 << 30))
            cout << 0 << ' ';
        else
            cout << dp [i] << ' ';
    return 0;
}