from heapq import heappop,heappush
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
E=[[] for i in range(n+1)]
for i in range(m):
x,y,c=map(int,input().split())
E[x].append((y,c))
E[y].append((x,c))
D=[1<<60]*(n+1)
FR=[-1]*(n+1)
D[1]=0
Q=[(0,1)]
while Q:
dis,x=heappop(Q)
if D[x]!=dis:
continue
for to,cost in E[x]:
if D[to]>dis+cost:
D[to]=dis+cost
heappush(Q,(D[to],to))
FR[to]=x
if FR[n]==-1:
print(-1)
else:
ANS=[n]
while ANS[-1]!=1:
ANS.append(FR[ANS[-1]])
print(*ANS[::-1])
#include<bits/stdc++.h>
using namespace std;
const long long inf=10e+15;
vector<pair<long long int ,long long int >>g[100001];
vector<long long int >dis(100001,inf);
long long int path[100001];
void dijkstra (int source)
{
priority_queue<pair<long long int ,long long int >>q;
q.push({source,0});
dis[source]=0;
while(!q.empty())
{
long long int a=q.top().first;
long long int b=q.top().second;
q.pop();
for(auto x:g[a])
{
long long int u=x.first;
long long int v=x.second;
if(dis[a]+v<dis[u])
{
dis[u]=dis[a]+v;
q.push({u,dis[u]});
path[u]=a;
}
}
}
}
int main()
{
int vertex,edgs;
cin>>vertex>>edgs;
for(int i=1; i<=edgs; i++)
{
int x,y,wt;
cin>>x>>y>>wt;
g[x].push_back({y,wt});
g[y].push_back({x,wt});
}
dijkstra(1);
path[1]=1;
if(path[vertex]==0)
cout<<"-1"<<endl;
else
{
int i=vertex;
vector<int>tmp;
while(i!=1)
{
tmp.push_back(i);
i=path[i];
}
reverse(tmp.begin(),tmp.end());
cout<<"1"<<' ';
for(int i=0; i<tmp.size(); i++)
{
cout<<tmp[i]<<' ';
}
}
}
50. Pow(x, n) | 43. Multiply Strings |
34. Find First and Last Position of Element in Sorted Array | 33. Search in Rotated Sorted Array |
17. Letter Combinations of a Phone Number | 5. Longest Palindromic Substring |
3. Longest Substring Without Repeating Characters | 1312. Minimum Insertion Steps to Make a String Palindrome |
1092. Shortest Common Supersequence | 1044. Longest Duplicate Substring |
1032. Stream of Characters | 987. Vertical Order Traversal of a Binary Tree |
952. Largest Component Size by Common Factor | 212. Word Search II |
174. Dungeon Game | 127. Word Ladder |
123. Best Time to Buy and Sell Stock III | 85. Maximal Rectangle |
84. Largest Rectangle in Histogram | 60. Permutation Sequence |
42. Trapping Rain Water | 32. Longest Valid Parentheses |
Cutting a material | Bubble Sort |
Number of triangles | AND path in a binary tree |
Factorial equations | Removal of vertices |
Happy segments | Cyclic shifts |