#include <bits/stdc++.h>

#define NM 50002
#define INF 1000000002

using namespace std;

vector < pair <int, int> > gr[NM];

int n, m;

bool viz[NM];
int dist[NM];

set < pair <int, int> > s;

void Dijkstra(int node)
{
    memset(dist, INF, sizeof(dist));
    s.insert(make_pair(0, node));
    dist[node] = 0;
    while(!s.empty())
    {
        auto f = s.begin();
        s.erase(f);
        auto fv = *f;
        if(viz[fv.second] == 1)
            continue;
        viz[fv.second] = 1;
        dist[fv.second] = fv.first;
        for(auto i : gr[fv.second])
            if(viz[i.first] == 0)
                s.insert(make_pair(i.second + dist[fv.second], i.first));
    }
}

int main()
{
    ifstream fin ("dijkstra.in");
    ofstream fout ("dijkstra.out");
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int a, b, c;
        fin >> a >> b >> c;
        gr[a].push_back(make_pair(b, c));
    }
    Dijkstra(1);
    for(int i = 2; i <= n; i++)
        fout << dist[i] << " ";
    fout << "\n";
    return 0;
}