/* DIJKSTRA */
#include <fstream>
#include <vector>
#include <set>

using namespace std;

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

#define DIM 50001
#define INF 0x3f3f3f3f

vector<vector<pair<int, int> > > v; // "matricea" de adiacenta
vector<int> dist; // dist[i] = distanta de la nodul 1 la nodul i
set<pair<int,int> > T; // distanta de la nodul 1 la nodul i && nr nodului
int n, m;
int a, b, c;

int distanta, nr, d, cost;

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

    dist = vector<int>(n + 1);
    v.resize(n + 1);

    for ( int i = 0; i < m; ++i )
    {
        fin >> a >> b >> c;
        v[a].push_back({b, c});
    }


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

    T.insert({0,1});

    while ( !T.empty() )
    {
        distanta = T.begin()->first;
        nr =       T.begin()->second;

        T.erase(T.begin());

        for ( auto p = v[nr].begin(); p != v[nr].end(); ++p )
        {
            d = (*p).first;
            cost = (*p).second;

            if ( dist[d] > distanta + cost )
            {
                dist[d] = distanta + cost;
                T.insert({dist[d],d});
            }
        }
    }

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



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