#include <fstream>
#include <vector>
#include <queue>

using namespace std;
vector<vector<pair<int, int>>> G;
vector<int> DP;
priority_queue<pair<int, int>> heap;
int N, M;

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

void readData()
{
    cin >> N >> M;
    G.resize(N + 1);
    DP.resize(N + 1);
    for (int i = 0; i <= N; ++i)
        DP[i] = 0x3f3f3f3f;
    for (int i = 0; i < M; ++i) {
        int a, b, cost;
        cin >> a >> b >> cost;
        G[a].emplace_back(cost, b);
    }
}

void dijkstra(int k)
{
    DP[k] = 0;
    heap.push({-0, k});
    while (!heap.empty()) {
        pair<int,int> top = heap.top();
        k = top.second;
        heap.pop();
        if (DP[k] != -top.first)
            continue;
        for (auto it : G[k])
            if (DP[it.second] > DP[k] + it.first) {
                DP[it.second] = DP[k] + it.first;
                heap.push({-DP[it.second], it.second});
            }
    }
    for (int i = 2; i <= N; ++i)
          if (DP[i] == 0x3f3f3f3f)
              cout << 0 << " ";
         else
              cout << DP[i] << " ";
     cout << "\n";
}

int main()
{
    cin.sync_with_stdio(false);
    cin.tie(0);

    readData();
    dijkstra(1);
    return 0;
}