#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n, m, x, y, lg;
int dist[50001];
vector < pair < int, int > > v[50001];

bool cmp(pair < int, int > a, pair < int, int > b)
{
    return a.second < b.second;
}

void dijkstra(int nod)
{
    queue < int > coada;
    coada.push(nod);
    while (!coada.empty())
    {
        nod = coada.front();
        coada.pop();

        for (int i=0; i<v[nod].size(); i++)
            if (!dist[v[nod][i].first])
            {
                dist[v[nod][i].first] = dist[nod] + v[nod][i].second;
                coada.push(v[nod][i].first);
            }
            else if (dist[nod] + v[nod][i].second < dist[v[nod][i].first])
            {
                dist[v[nod][i].first] = dist[nod] + v[nod][i].second;
                coada.push(v[nod][i].first);
            }
    }
}

int main()
{
    f >> n >> m;
    for (int i=1; i<=m; i++)
    {
        f >> x >> y >> lg;
        v[x].push_back(make_pair(y, lg));
    }

    //for (int i=1; i<=n; i++)
        //sort(v[i].begin(), v[i].end(), cmp);

    dijkstra(1);

    for (int i=2; i<=n; i++)
        g << dist[i] << " ";

    return 0;
}