#include <bits/stdc++.h>
#define inf 100000000
#pragma GCC optimize("O3")

using namespace std;

struct dik
{
    int val, lung;
    bool operator<(const dik &a) const
    {
        return lung > a.lung;
    }
};
vector<dik> ad[50001];
priority_queue<dik> q;
int f[50001];
void bfs()
{
    dik a, aux;
    int i;
    while (!q.empty())
    {
        a.val = q.top().val;
        a.lung = q.top().lung;
        q.pop();
        if (f[a.val] == a.lung)
        {
            for (i = 0; i < ad[a.val].size(); i++)
            {
                if (f[ad[a.val][i].val] > a.lung + ad[a.val][i].lung)
                {
                    aux.val = ad[a.val][i].val;
                    aux.lung = a.lung + ad[a.val][i].lung;
                    f[aux.val] = aux.lung;
                    q.push(aux);
                }
            }
        }
    }
}

int main()
{
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m, i, j, a, b, c;
    dik aux;
    cin >> n >> m;
    for (i = 0; i < m; i++)
    {
        cin >> a >> b >> c;
        aux.val = b;
        aux.lung = c;
        ad[a].push_back(aux);
    }
    for (i = 1; i <= n; i++)
        f[i] = inf;
    aux.val = 1;
    aux.lung = 0;
    f[1] = 0;
    q.push(aux);
    bfs();
    for (i = 2; i <= n; i++)
    {
        if (f[i] != inf)
            cout << f[i] << " ";
        else
            cout << 0 << " ";
    }
    return 0;
}