//                   //
//  O(m log n)       //
//                   //
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <numeric>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

const int INF = 100000000;


struct edg
{
    int x;
    int y;
    int w;
};

vector<edg> G;

vector<int> Q;

vector<int> d;

vector<int> tata;

int n,m,i,s;

bool sortare(edg a, edg b)
{
    if(a.x == b.x)
        return a.y <= b.y;
    else
        return a.x <= b.x;
}

void Dijkstra()
{
    Q.resize(n);
    for(i=1;i<=n;i++)
    {
        d[i] = INF;
        tata[i] = 0;
    }
    d[s] = 0;
    iota(Q.begin(),Q.end(),1);                  // Q = {1,2, ... n}
    while(!Q.empty())
    {
        int d_minim = INF;
        int u;                                                      // varf cu eticheta d[u] minima
        for(auto x : Q)
            if(d[x] <= d_minim) {
                d_minim = d[x];
                u = x;
            }
        Q.erase(remove(Q.begin(),Q.end(),u),Q.end());                   // Erase–remove idiom C++
        for(auto muchie : G)
        {
            if(muchie.x == u)
            {
                int v = muchie.y;
                if( d[u] + muchie.w < d[v])
                {
                    d[v] = d[u] + muchie.w;
                    tata[v] = u;
                }
            }
        }
    }
}


int main()
{
    in >> n >> m;
    G.resize(m);
    tata.resize(n+1);
    d.resize(n+1);
    for(i=0;i<m;i++)
    {
        in >> G[i].x >> G[i].y >> G[i].w;
    }
    sort(G.begin(),G.end(),sortare);            // convenienta la graf orientat

    s = 1;

    Dijkstra();

    for(i=s+1;i<=n;i++)
    {
	    fout << d[i] << " ";
    }

}