#include <fstream>
#include <iostream>
#include <queue>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,x,y,i,cost,d[50001],nodac,costac;
bool viz[50001];
vector<pair <int,int > > G[50001];
struct compare{
  bool operator()(pair<int,int> x, pair<int, int> y){
     return x.second>y.second;
  }

};
priority_queue<pair <int, int>, vector<pair <int, int> >, compare> heap;

int main()
{
    f>>n>>m;
    heap.push(make_pair(1,0));
    d[1]=0;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>cost;
        G[x].push_back(make_pair(y,cost));
    }
   while(!heap.empty()){
    pair<int,int> nod=heap.top();
    heap.pop();
    if(viz[nod.first]==1)
        continue;
    viz[nod.first]=1;
    for(i=0;i<G[nod.first].size();i++){
        nodac=G[nod.first][i].first;
        costac=G[nod.first][i].second;
        if(d[nodac]>d[nod.first]+costac){
            d[nodac]=d[nod.first]+costac;
            heap.push(make_pair(nodac,d[nodac]));
        }

    }
     heap.pop();

   }

    return 0;
}