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

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

class WeightedGraph{

    public:
        int to, cost;
};

const int maxV = 50000;
const int Inf = INT_MAX;

list <WeightedGraph> adjList[1 + maxV];
vector <int> dist;
bitset <1 + maxV> inHeap;
int V, E;

void readData(){

    fin >> V >> E;

    for(; E; --E){

        int from, to, cost;
        fin >> from >> to >> cost;

        adjList[from].push_back({to, cost});
    }
}

void Dijkstra(int node){

    dist.resize(1 + V);
    fill(dist.begin(), dist.end(), Inf);
    dist[node] = 0;

    priority_queue < pair <int ,int>, vector < pair <int, int> >, greater < pair <int, int> > > Heap;
    Heap.push({dist[node], node});
    inHeap[node] = true;

    while(!Heap.empty()){

        node = Heap.top().second;
        Heap.pop();
        inHeap[node] = false;

        for(const WeightedGraph &edge : adjList[node]){

            int nextNode = edge.to;
            int cost = edge.cost;

            if(dist[nextNode] > dist[node] + cost){

                dist[nextNode] = dist[node] + cost;
                if(!inHeap[nextNode]){

                    Heap.push({dist[nextNode], nextNode});
                    inHeap[nextNode] = true;
                }
            }
        }
    }
}

int main(){

    readData();
    Dijkstra(1);

    for(int node = 2; node <= V; ++node)
        if(dist[node] == Inf)
            fout << 0 << ' ';
        else fout << dist[node] << ' ';
}