#include <bits/stdc++.h>

using namespace std;

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

vector<pair<int, int>>h[50005];
priority_queue<pair<int, long long> >q;
int n, m, viz[50005];
long long d[50005];

void Dijkstra()
{
    q.push({1, 0});
    for(int i = 1; i <= n; i++)
        d[i] = 2e9;
    d[1] = 0;
    while(!q.empty())
    {
        int nod = q.top().first;
        q.pop();
        if(viz[nod] == 0)
            for(auto i : h[nod])
                if(d[nod] + i.second < d[i.first])
                {
                    d[i.first] = d[nod] + i.second;
                    q.push({i.first, -d[i.first]});
                }
        viz[nod] = 1;
    }

}

int main()
{
    int x, y, z;
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y >> z;
        h[x].push_back({y, z});
    }
    Dijkstra();
    for(int i = 2; i <= n; i++)
        fout << d[i] << " ";

    return 0;
}