#include <fstream>
#include <vector>
#include <set>

const int INF = 1000000000;
const int NMAX = 50011;

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

std :: set <std :: pair<int, int> > set;
std :: vector <std :: pair<int, int> >Graph[50010];
int dist[NMAX];
int n,m;


void dijkstra ( int source );

int main() {
    f >> n >> m;
    int v1, v2, value;
    for (int i = 1; i <= m; i++) {
        f >> v1 >> v2 >> value;
        Graph[v1].push_back(std :: make_pair(v2, value));
    }

    dijkstra(1);
}

void dijkstra (int src){

    for (int i = 1; i <= n; i++) {
        dist[i] = INF;
    }
    dist[src] = 0;
    set.insert(std :: make_pair(0, src));
    while (!set.empty()) {

        int source =set.begin() -> second;
        set.erase( set.begin() );

        for (int i=0; i < Graph[source].size(); i++){
            int destination = Graph[source][i].first;
            int value = Graph[source][i].second;

            if (dist[destination] > dist[source] + value){
                if (dist[destination] != INF)
                    set.erase (std ::  make_pair(dist[destination], destination));

                dist[destination] = dist[source] + value;
                set.insert (std :: make_pair(dist[destination], destination));
            }
        }
    }
    for (int i = 2; i <= n; i++) {
        if (dist[i] == INF)
            g << "0 ";
        else
            g<<dist[i]<<" ";
    }
 
}