#include <fstream>
#include <vector>
#include <utility>
#include <queue>
using namespace std;

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

struct Muchie
{
    int nod, cost;

    bool operator<(const Muchie& a) const
    {
        return a.cost < cost;
    }
};

int n, m;
int u, v, cost;
vector <Muchie> adj[50005];
int dp[50005];
priority_queue <Muchie> q;
bool ok[50005];

void dijkstra(int nod)
{
    for (int i = 1; i <= n; i++)
    {
        dp[i] = 1e9 + 5;
    }
    dp[nod] = 0;

    q.push({nod, dp[nod]});
    while (!q.empty())
    {
        Muchie curent = q.top();
        q.pop();

        ok[curent.nod] = false;
        for (const Muchie& x : adj[curent.nod])
        {
            if (dp[x.nod] > dp[curent.nod] + x.cost)
            {
                dp[x.nod] = dp[curent.nod] + x.cost;
                if (!ok[x.nod])
                {
                    ok[x.nod] = true;
                    q.push({x.nod, dp[x.nod]});
                }
            }
        }
    }
}
int main()
{
    cin >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        cin >> u >> v >> cost;
        adj[u].push_back({v, cost});
    }

    dijkstra(1);

    for (int i = 2; i <= n; i++)
    {
        cout << dp[i] << " ";
    }
    return 0;
}