# Dijkstra

Thu Sep 07 2023 13:58:18 GMT+0000 (Coordinated Universal Time)

Saved by @psisodiyaparek #c++

```#include <iostream>
#include <set>
#include <algorithm>
#include <math.h>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iterator>
// #include<bits/stdc++.h>
using namespace std;
#define forn(i, a, n) for (int i = a; i < n; i++)
#define MAXN 1000000
#define MOD 1000000007
#define INT_MAX 1e12
#define int long long
#define tc    \
int t;    \
cin >> t; \
while (t--)
#define TC size(arr) / size(arr[0])
#define Radhe ios::sync_with_stdio(false);
#define Krishna cin.tie(NULL);
void solve()
{
int n, m;
cin >> n >> m;
vector<vector<pair<int, int>>> adj(n);
map<pair<int, int>, int> mp;
vector<int> par(n, -1);
for (int i = 0; i < m; i++)
{
int u, v, w;
cin >> u >> v >> w;
if (u == v)
{
continue;
}
if (v < u)
{
swap(u, v);
}
u--, v--;

if (mp.count({u, v}))
{
mp[{u, v}] = min(mp[{u, v}], w);
}
else
{
mp[{u, v}] = w;
}
}

for  (auto i = mp.begin(); i != mp.end(); i++)
{ auto x=*i;
adj[x.first.first].push_back({x.first.second,x.second});
adj[x.first.second].push_back({x.first.first,x.second});
}

priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
vector<int> dist(n, INT_MAX);
dist[0] = 0;
pq.push({0, {0, -1}});
while (!pq.empty())
{
int u = pq.top().second.first;
if(pq.top().first>dist[u])
{
pq.pop();
continue;
}
par[u] = pq.top().second.second;
pq.pop();
for (auto it : adj[u])
{
int v = it.first;
int weight = it.second;
if (dist[u] == INT_MAX)
{
continue;
}
if (dist[v] > dist[u] + weight)
{
dist[v] = dist[u] + weight;
pq.push({dist[v], {v, u}});
}
}
}

if(dist[n-1]==INT_MAX)
{
cout<<-1<<endl;
return;
}
vector<int> ans;
int i = n - 1;
while (i != -1)
{
ans.push_back(i + 1);
i = par[i];
}
for(int i=ans.size()-1;i>0;i--)
{
cout<<ans[i]<<" ";
}
cout<<ans[0]<<endl;
}
int32_t main()
{
Radhe Krishna
{
solve();
}

return 0;
}
```
content_copyCOPY