#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n, m, dp[50005], viz[50005];
vector <pair<int, int> > a[50005];
priority_queue <pair<int, int> > q;
void Dijkstra(int x)
{
    for (int i = 1; i <= n; i++)
        dp[i] = INF;
    dp[x] = 0;
    q.push({ 0, x });
    
    while (!q.empty())
    {
        x = q.top().second;
        q.pop();
        if (viz[x] == 0)
        {
            viz[x] = 1;
            for (auto w : a[x])
            {
                if (w.first + dp[x] < dp[w.second])
                {
                    dp[w.second] = w.first + dp[x];
                    q.push({ -dp[w.second], w.second });
                }
            }
        }
    }
}

int main()
{
    int i, x, y, c;
    fin >> n >> m;
    while (m--)
    {
        fin >> x >> y >> c;
        a[x].push_back({ c, y });
    }

    Dijkstra(1);
    for (i = 2; i <= n; i++)
        fout << dp[i] << " ";
    

    return 0;
}