#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <cstring>

using namespace std;

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

int n, m;

struct Vecini {
    int vecin;
    int cost;
};

vector < Vecini > l[50005];
int dist[50005];
set < pair < int, int > > s;


int main()
{
    fin >> n >> m;

    int nod1, nod2, cost;

    for(int i = 1; i <= m; i++)
    {
        fin >> nod1 >> nod2 >> cost;

        l[nod1].push_back({nod2, cost});
    }

    s.insert({1, 0});

    memset(dist, 100, sizeof(dist));
    dist[1] = 0;

    while(!s.empty())
    {
        int nod = s.begin() -> first;
        int d = s.begin() -> second;
        s.erase(s.begin());

        for(auto elem : l[nod])
        {
            if(dist[elem.vecin] > dist[nod] + elem.cost)
            {
                dist[elem.vecin] = dist[nod] + elem.cost;
                s.insert({elem.vecin, elem.cost});
            }
        }
    }

    for(int i = 2; i <= n; i++)
        fout << dist[i] << ' ';

    fin.close();
    fout.close();
    return 0;
}