Dijkstra

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector < pair < int, ll > > G[ 100001 ];
ll dist[ 100001 ], ancestor[ 100001 ];
int main(){

  int n, m;
  cin >> n >> m;

  for(int i = 0; i < m; i ++){
    int a, b, c;
    cin >> a >> b >> c;
    G[ a ].push_back( {b,c} );
    G[ b ].push_back( {a,c} );
  }

  for(int i = 0; i <= n; i ++){
    dist[ i ] = 1e18;
  }

  dist[ 1 ] = 0;
  priority_queue < pair< ll, int > > Q;
  Q.push({0, 1});

  while(!Q.empty()){
    int act_node = Q.top().second;
    ll act_distance = -Q.top().first;
    Q.pop();

    for(auto w: G[ act_node ]){
      ll new_dist = act_distance + w.second;
      if(dist[w.first] > new_dist){
        dist[w.first] = new_dist;
        Q.push({-new_dist, w.first});
        ancestor[w.first] = act_node;
      }
    }
  }

//  for(int i = 1; i <= n; i ++) cout << i << " -> " << dist[ i ] << endl;

  if( dist[ n ] == 1e18 ){
    cout << -1 << endl;
    return 0;
  }

  int goal = n;
  vector < int > answer;
  while( goal != 0 ){
    answer.push_back(goal);
    goal = ancestor[ goal ];
  }
  reverse(answer.begin(), answer.end());
  for(auto a: answer){
    cout << a << " ";
  }

  return 0;
}