#include <bits/stdc++.h>

using namespace std;

ifstream si("dijkstra.in");
ofstream so("dijkstra.out");

vector <pair<int,int>> muchii[50001];

struct heap{
	int nod,dist;
}heap[250001];

int n,m,nr,rasp[50001],a,b,c;

void update(int nod; int dist){
	nr++;
	heap[nr].nod=nod;
	heap[nr].dist=dist;
	int poz=nr;
	while(poz>1){
		if(heap[poz/2].dist>heap[poz].dist){
			swap(heap[poz],heap[poz/2]);
			poz/=2;
		}
		else break;
	}
}

void delete_heap(){
	swap(heap[1];heap[nr]);
	nr--;
	int poz=1;
	while(2*poz+1<=nr && (heap[poz].dist>heap[poz*2].dist || heap[poz].dist>heap[poz*2+1].dist)){
		if(heap[poz*2].dist>heap[poz*2+1].dist){
			swap(heap[poz*2+1],heap[poz*2]);
			poz*=2;
			poz++;
		}
		else {swap(heap[poz*2],heap[poz]); poz*=2;}
		if(poz*2==nr && heap[poz].dist>heap[poz*2].dist) swap(heap[poz],heap[poz*2]);
	}
}

void dijkstra(){
	update(1,0);
	while(nr){
		nod=heap[1].nod;
		dist=heap[1].dist;
	}
	delete_heap();
	for(auto it:v[nod])
	if(rasp[it.first]==-1) update(it.first,it.second+dist);
}

int main(){

si>>n>>m;
for(int i=1;i<=m;i++){
	si>>a>>b>>c;
	v[a].push_back({b,c});
}
dijkstra();
for(int i=0;i<;i++){
	so<<rasp[i];
}

return 0;
}