#include <iostream>
#include <fstream>
#include <queue>
#include <string>
#include <vector>
#include <stack>
#include <map>
#include <algorithm>

using namespace std;

const int INF = 0x3f3f3f3f;
const string InputFile = "dijkstra.in";
const string OutputFile = "dijkstra.out";

class Comparator{
public:
    bool operator () (const pair<int, int>& a, const pair<int,int>& b) {
        return a.second < b.second;
    }
};

typedef unsigned int uint32_t;
typedef vector< vector< pair<int,int> > > Graph;
typedef priority_queue< pair<int,int>, vector< pair<int,int> >, Comparator > Heap;

istream& operator >> (istream& stream, Graph& graph) {
    uint32_t n, m;
    stream >> n >> m;
    graph.resize(n+1);

    for (uint32_t i = 0; i < m; ++i) {
        int src, dst, cost;
        stream >> src >> dst >> cost;
        graph[src].push_back(make_pair(dst, cost));
    }
    return stream;
}

ostream& operator << (ostream& stream, vector<int>& v) {
    for (auto it = v.begin()+2; it < v.end(); ++it) {
        stream << ((*it) == INF ? 0 : (*it)) << ' ';
    }
    return stream;
}

vector<int> dijkstra(int source, Graph& graph) {
    vector<int> distances(graph.size(), INF);
    vector<bool> visited(graph.size(), 0);
    Heap myHeap;

    distances[source] = 0;
    myHeap.push(make_pair(source, distances[source]));

    while (!myHeap.empty()) {
        //elimin nodurile deja vizitate la care am ajuns cu cost mai bun
        while (!myHeap.empty() && visited[myHeap.top().first]) 
            myHeap.pop();
        if (myHeap.empty())
            break;

        pair<int,int> edge = myHeap.top();
        myHeap.pop();
        
        int node = edge.first;
        visited[node] = true;
        for (auto it = graph[node].begin(); it < graph[node].end(); ++it) 
            if (distances[it->first] > distances[node] + it->second) {
                distances[it->first] = distances[node] + it->second;
                myHeap.push(make_pair(it->first, distances[it->first])); 
            }
    }
    return distances;
}

int main(void) {
    ifstream fin(InputFile);
    ofstream fout(OutputFile);
    
    Graph graph;
    vector<int> distances;

    fin >> graph;
    distances = dijkstra(1, graph);
    fout << distances;

    fin.close(); fout.close();
    return 0;
}