#include <fstream>
#include <vector>
#include <queue>

using namespace std ;

#define NMax 50005
#define oo 1 << 30

vector< pair <int, int> > G[NMax] ;
int D[NMax] ;
bool inQueue[NMax] ;

int N, M ;
int P = 1 ;

struct cmp {
    bool operator() (int x, int y) {
        return D[x] > D[y] ;
    }
};

priority_queue<int, vector<int>, cmp> Queue ;

void dijkstra(int startNode) {
    for(int i = 1 ; i <= N ; i++) {
        D[i] = oo ;
    }
    D[startNode] = 0 ;
    inQueue[startNode] = true ;
    Queue.push(startNode) ;

    while(!Queue.empty()) {
        int currentNode = Queue.top() ;
        Queue.pop() ;
        inQueue[currentNode] = false ;

        for(size_t i = 0 ; i < G[currentNode].size() ; i++) {
            int neighbor = G[currentNode][i].first ;
            int cost = G[currentNode][i].second ;

            if(D[currentNode] + cost < D[neighbor]) {
                D[neighbor] = D[currentNode] + cost ;

                if(!inQueue[neighbor]) {
                    inQueue[neighbor] = true ;
                    Queue.push(neighbor) ;
                }
            }
        }
    }
}

void read() {
    ifstream f("dijkstra.in") ;
    f >> N >> M ;
    int x, y, c ;
    for(int i = 0 ; i < M ; i++) {
        f >> x >> y >> c ;
        G[x].push_back(make_pair(y, c)) ;
    }
    f.close() ;
}

void write() {
    ofstream g("dijkstra.out") ;
    for(int i = 2 ; i <= N ; i++) {
        g << (D[i] != oo ? D[i] : 0) << ' ' ;
    }
    g.close() ;
}

int main() {
    read() ;
    dijkstra(P) ;
    write() ;
    return 0 ;
}