#include<fstream>
#include<list>
#include<queue>
#include<climits>

using namespace std;

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

struct graph{

    int nod, cost;
};

const int Nmax = 50005, inf = INT_MAX;

int dist[Nmax], n, m, x, y, c, node, current_node, new_node, new_cost;
bool viz[Nmax];

list<graph>l[Nmax];
list<graph>::iterator it;

struct cmp{

    bool operator()(const int &a, const int &b) const{

        return dist[a] > dist[b];
    }
};

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

void read_data(){

    f >> n >> m;
    while(f >> x >> y >> c)
        l[x].push_back({y, c});
}

void dijkstra(int node){

    viz[node] = true;
    pq.push(node);

    for(int i = 1; i <= n; i++)
        dist[i] = inf;
    dist[node] = 0;

    while(!pq.empty()){

        current_node = pq.top();
        pq.pop();

        viz[current_node] = false;

        for(it = l[current_node].begin(); it != l[current_node].end(); it++){

            new_node = it->nod;
            new_cost = it->cost;
            if(dist[new_node] > dist[current_node] + new_cost){

                dist[new_node] = dist[current_node] + new_cost;

                if(!viz[new_node]){

                    viz[new_node] = true;
                    pq.push(new_node);
                }
            }
        }
    }
}

void write_data(int node){

    for(int j = 1; j <= n; j++)
        if(j != node){

           if(dist[j] == inf)
            g << 0 << ' ';
           else
            g << dist[j] << ' ';
        }
}

int main(){

    read_data();
    dijkstra(1);
    write_data(1);
}