#include<vector>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
struct edge{
int e,w;
};
vector<edge> V[10000];//Graph Data
int dist[10000]; //Save the distance from S
bool inst[10000];//Flag of if the points have being in stack
int N,M,S,E;
int main(){
int a,b,w;
while(~scanf("%d%d",&N,&M)){
for(int i=0;i<N;++i)V[i].clear();
memset(dist,0x3f,sizeof(dist)); //init to INF
memset(inst,false,sizeof(inst));//init to false
while(M--){
scanf("%d%d%d",&a,&b,&w);
V[a].push_back((edge){b,w});//Add edge
V[b].push_back((edge){a,w});
}
scanf("%d%d",&S,&E);
//Algorithm:SPFA
dist[S]=0;
queue<int> st; //push the S into stack and set dist[S]=0
st.push(S); //point : don't set inst[S]=true; it is foolish!
while(!st.empty()){//loop until stack is empty
int t=st.front();st.pop();
inst[t]=false;
for(edge &e:V[t]){//for C++11
if(dist[e.e]>dist[t]+e.w){//Relax
dist[e.e]=dist[t]+e.w;
if(!inst[e.e]){//if point don't stay in stack, push it in
st.push(e.e);
inst[e.e]=true;
}
}
}
}
printf("%d\n",dist[E]);
}
}
#include<vector>
#include<cstdio>
#include<cstring>
#include<queue>
#include<iostream>
using namespace std;
struct edge{
int s,e,w;
};
vector<edge> e;
int dist[10000]; //Save the distance from S
int N,M,S,E;
int main(){
int a,b,w;
while(~scanf("%d%d",&N,&M)){
memset(dist,0x3f,sizeof(dist)); //init to INF
while(M--){
scanf("%d%d%d",&a,&b,&w);
e.push_back((edge){a,b,w});
e.push_back((edge){b,a,w});
}
scanf("%d%d",&S,&E);
//Algorithm:Bellman-Ford
dist[S]=0;
while(true){
bool update=false;
for(edge &t:e){
if(dist[t.e]>dist[t.s]+t.w){
dist[t.e]=dist[t.s]+t.w;
update=true;
}
}
if(!update)break;
}
printf("%d\n",dist[E]);
}
}
#include<vector>
#include<cstdio>
#include<cstring>
#include<queue>
#include<iostream>
using namespace std;
struct edge{
int e,w;
};
inline bool operator<(const edge &a,const edge &b){
return a.w>b.w; //Notice!
}
vector<edge> V[10000];//Graph Data
int dist[10000]; //Save the distance from S
int N,M,S,E;
int main(){
int a,b,w;
while(~scanf("%d%d",&N,&M)){
for(int i=0;i<N;++i)V[i].clear();
memset(dist,0x3f,sizeof(dist)); //init to INF
while(M--){
scanf("%d%d%d",&a,&b,&w);
V[a].push_back((edge){b,w});//Add edge
V[b].push_back((edge){a,w});
}
scanf("%d%d",&S,&E);
//Algorithm:Dijkstra with Priority Queue
priority_queue<edge> pq;
pq.push((edge){S,0});
while(!pq.empty()){
edge t=pq.top();pq.pop();
if(t.e==E){
dist[t.e]=t.w;
break; //Find answer!
}
if(dist[t.e]!=0x3f3f3f3f)continue;
dist[t.e]=t.w;
for(edge &e:V[t.e])
if(dist[e.e]>dist[t.e]+e.w)
pq.push((edge){e.e,dist[t.e]+e.w});
}
printf("%d\n",dist[E]);
}
}