#include 
#include 
#include 
#include 
#include 
#include 
#define ll long long
#define ps push_back
using namespace std;
struct node{
    int idx;
    ll shortest_path;
    
    node(int i,ll s){
        idx = i;
        shortest_path = s;
    }
    bool operator < (const node &tmp) const {
        return shortest_path > tmp.shortest_path;
    }
};
vector> graph[100050];
int main() {
    int n,m;
    cin >>n >> m;
    
    for(int i = 0;i> a >> b>> c;
        graph[a].push_back(make_pair(b, c));
//        graph[b].push_back(make_pair(a, c));
    }
   
 
        priority_queue pq;
        vector dist(n+1,1e18);
        vector visited(n+1,false);
        dist[1] = 0;
        pq.push(node(1,0));
    
        while(!pq.empty()){
            node curr = pq.top();
            pq.pop();
            
            if(visited[curr.idx]) continue;
            visited[curr.idx] = true;
            for(int j = 0;j