#include <iostream>
#include <fstream>
#include <vector>
#include <set>
using namespace std;
int N, M;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
vector<vector<pair<int,int>>> graph;
vector<int> distances;
struct PairComp {
    template <typename U, typename V>
    bool operator()(const pair<U,V>& a, const pair<U,V>& b) const {
        if (a.second == b.second) {
            return a.first < b.first;
        } else {
            return a.second < b.second;
        }
    }
};
void read_input()
{
    in >> N >> M;
    graph.resize(N + 1);
    for (int i = 0; i < M; i++) {
        int x, y, z;
        in >> x >> y >> z;
        graph[x].push_back(make_pair(y,z)); 
    }
}
void dijkstra()
{

    set<pair<int, int>, PairComp> q;
    vector<bool> visited(N+1, false);
    distances.resize(N+1);
    q.insert(make_pair(1, 0));
    while (!q.empty())
    {
        int curNode = q.begin()->first;
        int curDist = q.begin()->second;
       // cout << curNode << "," << curDist << "\n";
        q.erase(q.begin());
        if (visited[curNode]) {
            continue;
        } else {
            visited[curNode] = true;
            distances[curNode] = curDist;
            for (int i = 0; i < graph[curNode].size(); i++) {
                int neigh = graph[curNode][i].first;
                int edgeLen = graph[curNode][i].second;
                if (!visited[neigh]) {
                    q.insert(make_pair(neigh, edgeLen + curDist));
                }
            }
        }

    }
}
void print()
{
    for (int i = 2; i < N+1; i++) {
        out << distances[i] << " ";
    }
    out << "\n";
}
int main()
{
    read_input();
    dijkstra();
    print();
    return 0;
}