# Code Forces 26C Dijkstra?

C. Dijkstra?

time limit per test

1 second

memory limit per test

64 megabytes

input

standard input

output

standard output

You are given a weighted undirected graph. The vertices are enumerated from 1 to n. Your task is to find the shortest path between the vertex 1 and the vertex n.

Input

The first line contains two integers n and m (2 ≤ n ≤ 105, 0 ≤ m ≤ 105), where n is the number of vertices and m is the number of edges. Following m lines contain one edge each in form aibi and wi (1 ≤ ai, bi ≤ n, 1 ≤ wi ≤ 106), where ai, bi are edge endpoints and wi is the length of the edge.

It is possible that the graph has loops and multiple edges between pair of vertices.

Output

Write the only integer -1 in case of no path. Write the shortest path in opposite case. If there are many solutions, print any of them.

Examples

input

```5 6
1 2 2
2 5 5
2 3 4
1 4 1
4 3 3
3 5 1```

output

`1 4 3 5 `

input

```5 6
1 2 2
2 5 5
2 3 4
1 4 1
4 3 3
3 5 1```

output

`1 4 3 5 `

```#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <queue>
#include <stdio.h>
#include <vector>

using namespace std;
const long long int INF=(long long int )1<<60;
#define MAX 100000
vector< pair<int,int> > a[MAX+5];
struct Node
{
int pos;
int value;
Node(){};
Node(int pos,int value)
{
this->pos=pos;
this->value=value;
}
friend bool operator <(Node a,Node b)
{
return a.value>b.value;
}
};
priority_queue<Node>q;
int vis[MAX+5];
long long int d[MAX+5];
int pre[MAX+5];
int n,m;
void Dijstra()
{
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++)
d[i]=INF;
pre[1]=-1;
d[1]=0;
q.push(Node(1,0));
while(!q.empty())
{
Node term=q.top();
q.pop();
if(vis[term.pos]) continue;
vis[term.pos]=1;

for(int i=0;i<a[term.pos].size();i++)
{
int v=a[term.pos][i].first;
int w=a[term.pos][i].second;
if(!vis[v]&&d[term.pos]+w<d[v])
{
d[v]=d[term.pos]+w;
pre[v]=term.pos;
q.push(Node(v,d[v]));
}
}
}
}
void print(int x)
{
if(x==-1)
return;
print(pre[x]);
if(x==n)
cout<<x<<endl;
else
cout<<x<<" ";
}
int main()
{

scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
a[i].clear();
int x,y,z;

for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
a[x].push_back(make_pair(y,z));
a[y].push_back(make_pair(x,z));
}
Dijstra();
if(d[n]==INF)
printf("-1\n");
else
print(n);
return 0;
}```

500 篇文章45 人订阅

0 条评论

## 相关文章

37710

365160

92130

### python operator模块学习

operator模块是python中内置的操作符函数接口，它定义了一些算术和比较内置操作的函数。operator模块是用c实现的，所以执行速度比python代码...

9020

37770

### C语言第四讲,typedef 关键字,以及作用域

C语言第四讲,typedef 关键字,以及作用域 一丶typedef关键字 　　在C语言中,有typedef 关键字,这个关键字的作用就是允许你...

29550

### 29.C++- 异常处理

C++内置了异常处理的语法元素 try catch try语句处理正常代码逻辑 当try语句发现异常时,则通过throw语句抛出异常,并退出try语句 catc...

30360

34250

### 理解js中的new

new 操作符 在有上面的基础概念的介绍之后，在加上new操作符，我们就能完成传统面向对象的class + new的方式创建对象，在Javascript中，我们...

42940

15140