记录编号	259068	评测结果	AAAAAAAAAA
题目名称	KZ菌的星际旅行	最终得分	100
用户昵称	哒哒哒哒哒！	是否通过	通过
代码语言	C++	运行时间	0.163 s
提交时间	2016-05-08 07:13:28	内存使用	19.39 MiB

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue> 
#define maxn 1000001
#define maxm 1000001
using namespace std;
 
int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-48;
		ch=getchar();
	}
	return x*f;
}
struct Edge{
	int next,to,dis;
}e[maxm];
int head[maxn],tot,dis[maxn];
void edge(int u,int v,int w){
	e[++tot].to=v;
	e[tot].next=head[u];
	e[tot].dis=w;
	head[u]=tot;
}
struct Node{
	int num,dist;
	Node(int x,int y){num=x,dist=y;}
		bool operator < (const Node &x)const{
		return dist>x.dist;
	}
};	
void dijkstra(int s){
	priority_queue<Node>q;
	memset(dis,127/3,sizeof(dis));
	dis[s]=0;q.push(Node(s,0));
	while(!q.empty()){
		Node node=q.top(); q.pop();
		s=node.num;
		if(dis[s]!=node.dist) continue;
		for(int i=head[s];i;i=e[i].next){
			int to=e[i].to;
			if(dis[to]>dis[s]+e[i].dis){
				dis[to]=dis[s]+e[i].dis;
				q.push(Node(to,dis[to]));
			}
		}
	}	
}
int main()
{
	freopen("KZstartravelillu.in","r",stdin);
	freopen("KZstartravelillu.out","w",stdout);
	int t=read(),m=read();
	for(int i=1;i<=m;i++){
		int a=read(),b=read(),c=read();
		edge(a,b,c);
		edge(b,a,c);
	}
	dijkstra(1);
	printf("%d",dis[t]*2);
	return 0;
}