#include <fstream>
#include <cstring>
#include <queue>

#define mp make_pair
#define pb push_back

using namespace std ;

typedef pair <int, int> Pair ;

const int NMAX = 50005 ;
const int INF = 0x3f3f3f3f ;

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

int N, M ;
vector <Pair> V[NMAX] ;
int D[NMAX];
queue <int> Q ;


inline void DIJKSTRA()
{
    Q.push(1) ;
    D[1] = 0 ;

    while(!Q.empty())
    {
        int nod = Q.front() ;
        Q.pop() ;

        for(vector <Pair> ::iterator it = V[nod].begin() ; it != V[nod].end() ; ++ it)
            if(D[it -> first] > D[nod] + it -> second )
            {

                D[it -> first] = D[nod] + it -> second ;
                Q.push(it -> first) ;
            }
    }

}

int main()
{
    fin >> N >> M ;

    for(int i = 1 ; i <= N ; ++ i)
    {
        int XX, YY, cost ;
        fin >> XX >> YY >> cost ;
        V[XX].pb(mp(YY, cost)) ;
    }

    memset(D, INF, sizeof D) ;

    DIJKSTRA() ;

    for(int i = 2 ; i <= N ; ++ i)
        fout << (D[i] != INF ? D[i] : 0) << ' ' ;

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