#include <stdio.h>
#include <vector>

#define MAXN 50000
#define MAXNPOW2 65536
#define INFINIT 1000000001

using namespace std;

struct muchie{
	int nod, cost;
};

struct nod{
    int cost, viz;
};

vector<muchie> lista[MAXN];
nod noduri[MAXN];

int n, m, npow2;

struct fen{
    int v[MAXNPOW2*2];
    void build(){
        for(int i=npow2-1;i>0;i--){

        }
    }
    void update(int pos){

    }
};

fen aint_min;

void dijkstra(int poz){
	int cn;
	unsigned int i;
	npow2=1<<__builtin_clz(n-1);
    noduri[poz].cost=0;
    cn=n-1;
    while(cn--){
        aint_min.update(poz);
        for(i=0;i<lista[poz].size();i++){
			if(!noduri[lista[poz][i].nod].viz){
				if(noduri[poz].cost+lista[poz][i].cost<noduri[lista[poz][i].nod].cost){
					noduri[lista[poz][i].nod].cost=noduri[poz].cost+lista[poz][i].cost;
                    aint_min.update(lista[poz][i].nod);
				}
			}
        }
        noduri[poz].cost=INFINIT;
		noduri[poz].viz=1;
		aint_min.update(poz);
        poz=aint_min.v[1];
    }
}

void read_and_build_graph(){
	muchie aux;
	int i, n1, n2, cost;
    scanf("%d%d", &n, &m);
    for(i=0;i<m;i++){
        scanf("%d%d%d", &n1, &n2, &cost);
        n1--;
        n2--;
        aux.nod=n2;
        aux.cost=cost;
        lista[n1].push_back(aux);
    }
}

int main()
{
	read_and_build_graph();
	dijkstra(0);
    return 0;
}