#include <stdio.h>
#include <string.h>
#include <vector>
#define N 220

using namespace std;

struct Road{
	int next;
	int dis;
};

vector<Road>City[N];
int CityNum, RoadNum;
int dij[N];
bool vis[N];

void Init(){
	memset(vis, 0, sizeof(vis));
	for(int i = 0; i <= CityNum; i ++){
		City[i].clear();
		dij[i] = 0xfffffff;
	}
}
void Dijistra(int cur){
	dij[cur] = 0;
	while(vis[cur] == 0){
		vis[cur] = 1;
		for(int i = 0; i < City[cur].size(); i ++){
			int next = City[cur].at(i).next;
			int dis = City[cur].at(i).dis;
			if(dij[next] > dij[cur] + dis){
				dij[next] = dij[cur] + dis;
			}
		}
		int min = 0xfffffff;
		for(int i = 0; i < CityNum; i ++){
			if(!vis[i] && min > dij[i]){
				min = dij[i];
				cur = i;
			}
		}
	}
}

int main()
{
	Road nw;
	while(scanf("%d%d", &CityNum, &RoadNum) != EOF){
		Init();
		int start, end, distance;
		for(int i = 0; i < RoadNum; i ++){
			scanf("%d%d%d", &start, &end, &distance);
			nw.next = start;
			nw.dis = distance;
			City[end].push_back(nw);
			nw.next = end;
			City[start].push_back(nw);			
		}
		scanf("%d%d", &start, &end);
		
		Dijistra(start);
		
		if(dij[end] == 0xfffffff){
			printf("-1\n");
		}
		else{
			printf("%d\n", dij[end]);
		}
	}
	
	return 0;
}

#include <stdio.h>
#include <algorithm>
#define N 205

using namespace std;

int map[N][N];
int CityNum, RoadNum;

int floyd(int start, int end){
    for(int k = 0; k < CityNum; k ++){
        for(int i = 0; i < CityNum; i ++){
            for(int j = 0; j < CityNum; j ++){
                map[i][j] = min(map[i][j], map[i][k] + map[k][j]);
            }
        }
    }
    
    return map[start][end] < 0xfffffff ? map[start][end] : -1;
}

int main()
{
    int start, end, len;
    while(scanf("%d%d", &CityNum, &RoadNum) != EOF){
        for(int i = 0; i < CityNum; i ++){
            for(int j = 0; j < CityNum; j ++){
                map[i][j] = (i == j ? 0 : 0xfffffff);
            }
        }
            
        for(int i = 0; i < RoadNum; i ++){
            scanf("%d%d%d", &start, &end, &len);
            if(len < map[start][end]){				// 注使用邻接矩阵时 需判断重连 
				map[end][start] = map[start][end] = len;		// 无向图 
			}
        }
        scanf("%d%d", &start, &end);
        
        int ans = floyd(start, end);
        
        printf("%d\n", ans);
    }
    
    return 0;
}

#include <stdio.h>

struct ROAD{
	int from;
	int to;
	int len;
};

ROAD Road[2020];
int CityNum, RoadNum;
int dis[220];

void Bellman_Ford(int start){
	for(int i = 0; i < CityNum; i ++){
		dis[i] = 0xfffffff;
	}
	dis[start] = 0;
	for(int i = 0; i < CityNum; i ++){
		for(int j = 0; j < RoadNum * 2; j ++){
			if(dis[Road[j].to] > dis[Road[j].from] + Road[j].len){
				dis[Road[j].to] = dis[Road[j].from] + Road[j].len;
			}
		}
	}
}

int main()
{
	int start, end;
	while(scanf("%d%d", &CityNum, &RoadNum) != EOF){
		for(int i = 0; i < RoadNum; i ++){
			scanf("%d%d%d", &Road[i].from, &Road[i].to, &Road[i].len);
			Road[RoadNum + i].from = Road[i].to;
			Road[RoadNum + i].to = Road[i].from;
			Road[RoadNum + i].len = Road[i].len;
		}
		scanf("%d%d", &start, &end);
		
		Bellman_Ford(start);
		
		if(dis[end] == 0xfffffff){
			printf("-1\n");
		}
		else{
			printf("%d\n", dis[end]);
		}
	}
	
	return 0;
}

#include <stdio.h>
#include <string.h>
#include <queue>
#define N 220

using namespace std;

int CityNum, RoadNum;
int map[N][N], dis[N];
bool vis[N];

void Init(){
	memset(vis, 0, sizeof(vis));
	for(int i = 0; i < CityNum; i ++){
		dis[i] = 0xfffffff;
		for(int j = 0; j < CityNum; j ++){
			map[i][j] = 0xfffffff;
		}
	}
}

void SPFA(int start){
	queue<int>q;
	q.push(start);
	dis[start] = 0;
	while(!q.empty()){
		int cur = q.front();
		q.pop();
		vis[cur] = 0;
		
		for(int i = 0; i < CityNum; i ++){
			if(dis[i] > map[cur][i] + dis[cur]){
				dis[i] = map[cur][i] + dis[cur];
				if(!vis[i]){
					q.push(i);
					vis[i] = 1;
				}
			}
		}
	}	
}

int main()
{
	int start, end, len;
	while(scanf("%d%d", &CityNum, & RoadNum) != EOF){
		Init();
		for(int i = 0; i < RoadNum; i ++){
			scanf("%d%d%d", &start, &end, &len);
			if(map[start][end] > len){
				map[start][end] = map[end][start] = len;
			}
		}
		scanf("%d%d", &start, &end);
		
		SPFA(start);
		
		if(dis[end] == 0xfffffff){
			printf("-1\n");
		}
		else{
			printf("%d\n", dis[end]);
		}
	}
	
	return 0;
}