#include <bits/stdc++.h>
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
///summax

priority_queue<pair<int, int>> q;
vector<pair<int,int>> L[50005];
bitset<50005> v;
int d[50005];
int n, m;

void Dijkstra(int k)
{
    int x;
    q.push({0, k});
    d[k] = 0;
    while(!q.empty())
    {
        x = q.top().second;
        q.pop();
        if(v[x] == 0)
        {
            v[x] = 1;
            for(auto w : L[x])
                if(d[w.second] > w.first + d[x])
                {
                    d[w.second] = w.first + d[x];
                    q.push({-d[w.second], w.second});
                }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    fin.tie(0);
    fout.tie(0);
    int i, x, y, c;
    fin >> n >> m;
    for(i=1; i<=m; i++)
    {
        fin >> x >> y >> c;
        L[x].push_back({c,y});
    }
    for(i=1; i<=n; i++)
        d[i] = 2e9;
    Dijkstra(1);
    for(i=2; i<=n; i++)
        fout << d[i] << " ";
    fin.close();
    fout.close();
    return 0;
}