// 负环：
// 如果一个环上，环上各边的权值之和是负数
// 负环
// spfa 判负环

// 1, 队列，如果一个点入队出队次数超过 n

// 2. dis[v] , cnt[v] 记录到达 v 这个点经过几条边
//       如果经过 的边的数量大于等于 n ，负环

bool spfa() {
	queue<int> q;
	memset(vis, 0, sizeof vis);
	memset(dis, 0x3f, sizeof dis);
	memset(cnt, 0, sizeof cnt);
	dis[1] = 0;
	q.push(1)
	vis[1] = 1;
	while (q.size()) {
		int u = q.front();
		q.pop();
		vis[u] = 0;
		for (int i = head[u]; i ; i = nxt[i]) {
			int v = ver[i];
			int w = edge[i];
			if (dis[v] > dis[u] + w) {
				dis[v] = dis[u] + w;
				// cnt[v] 用来统计到达 v 的时候经过的边的数量
				cnt[v] = cnt[u] + 1; // 多了一条边
				if (cnt[v] >= n)
					return 1; // 存在负环
				if (vis[v])
					continue;
				vis[v] = 1;
				q.push(v);
			}
		}
	}
	return 0;
}

// 边可以重复经过
// 严格最短路

//从 1 - i 来了一个路径，长度 是 x
//1. 比之前的最短路短， 新的第一名
//	之前的最短路变成次短路，
//	x 变成新的最短路
//2. 比之前的最短路长，比次短路短 新的第二名
//	x 变成次短路
//3. x 比次短路长， 丢了

//int dis[N][2];
//dis[i][0] 记录到 i 的最短路长度
//dis[i][1] 记录到 i 的次短路长度
#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 10;
const int M = 1e5 + 10;
int n, m;
int head[N], ver[M << 1], edge[M << 1], nxt[M << 1], tot;
int dis[N][2];

void add(int x, int y, int z) {
	tot++;
	ver[tot] = y;
	edge[tot] = z;
	nxt[tot] = head[x];
	head[x] = tot;
}

void dijkstra() {
	memset(dis, 0x3f, sizeof dis);
	dis[1][0] = 0;
	priority_queue<pair<int, int>>q;
	q.push({0, 1});
	while (q.size()) {
		int u = q.top().second;
		int s = -q.top().first;
		q.pop();
		// 直接舍弃
		if (s > dis[u][1])
			continue;
		for (int i = head[u] ; i ; i = nxt[i]) {
			int v = ver[i];
			int w = edge[i];
			if (dis[v][0] > s + w) { // 新的第一名
				dis[v][1] = dis[v][0];
				dis[v][0]  = s + w;
				q.push({-dis[v][0], v});
				q.push({-dis[v][1], v});
			}
			if (s + w > dis[v][0] && s + w < dis[v][1]) {
				dis[v][1] = s + w;
				q.push({-dis[v][1], v});
			}
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		add(x, y, z);
		add(y, x, z);
	}
	dijkstra();
	cout << dis[n][1];
	return 0;
}

// 次短路：第二短的路
// 最短路，
// 分类：
// 1. 边可以重复经过; 边不可以重复经过
// 2. 严格次短路；非严格次短路，

// 边不可以重复经过
//// 删边法：
//1. 跑一遍最短路，记录下来所有的边
//// pre 数组，记录到达当前点之前的点
//// 边 pre[i] , i
//2. 依次删除路径里面的边，再跑最短路
//3. 取一个最小值，最小的值就是次短路
//a <b  严格小  1 2
//a <= b 非严格 1 1
// 非严格最短路，边不可以重复经过
// 删边法
//两点之间的距离公式
//sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2))
#include <bits/stdc++.h>
using namespace std;
const int N = 2e2 + 10;
const int M = 2e4 + 10;
int head[N], ver[M], nxt[M],  tot;
double edge[M];
int x[N], y[N];  // 记录点的坐标
bool vis[N];
double dis[N];

void add(int x, int y, double z) {
	tot++;
	edge[tot] = z;
	nxt[tot] = head[x];
	head[x] = tot;
	ver[tot] = y;
}

double f(int i, int j) {
	double sum = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
	return sqrt(sum);
}

int n, m, pre[N];  // pre  记录来的点，记录最短路径经过的点

void dijkstra(int dx, int dy) {
	memset(vis, 0, sizeof vis);
	for (int i = 1; i <= n; i++)
		dis[i] = 1e9;
	dis[1] = 0;
	priority_queue<pair<double, int>> q;
	q.push({0, 1});
	while (q.size()) {
		int u =  q.top().second;
		q.pop();
		if (vis[u])
			continue;
		vis[u] = 1;
		for (int i = head[u] ; i ; i = nxt[i]) {
			int v = ver[i];
			double w  = edge[i];
			// 判断是不是要删除的边,如果是就删除
			if (u == dx && v == dy || u == dy && v == dx)
				continue;
			if (dis[v] > dis[u] + w) {
				dis[v] = dis[u] + w;
				q.push({-dis[v], v});
				// 记录前驱节点
				if (dx == -1 && dy == -1)
					pre[v] = u;
			}
		}
	}
}


int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> x[i] >> y[i];
	for (int i = 1; i <= m; i++) {
		int xx, yy;
		cin >> xx >> yy;
		double w = f(xx, yy);
		add(xx, yy, w);
		add(yy, xx, w);
	}
	// 跑一个原始最短路
	dijkstra(-1, -1); // -1 -1 ,代表不用删除边，
	double res = 1e9;
	// 遍历要删除的边，删除跑最短路
	for (int i = n; i != 1 ; i = pre[i]) {
		dijkstra(i, pre[i]);
		res = min(res, dis[n]);
	}
	if (res == 1e9)
		cout << -1;
	else
		printf("%.2lf", res);
	return 0;
}

/*
  对于没有速度的点来说，到达这个点的速度是有很多种可能的
  因此记录最短路的时候，也记录下来到达这个点的时候的速度

  分层图最短路，但是分层图不好建立
  所以我们通过 f[N][V] 来体现分层图
 */
#include <bits/stdc++.h>
using namespace std;
const int N = 200;
const int M = 22510;
int n, m, d;
// v 记录的当前点速度,edge 记录的是当前的长度
int head[N], ver[M], edge[M], value[M], nxt[M], tot;
// 求的是最短的时间， edge / v
double f[N][501];
bool vis[N][501];

pair<int, int> ans[N][501]; // 记录的是到达点i和速度为v的点的上一个转移来的位置

void add(int a, int b, int vv, int l) {
	tot++;
	ver[tot] = b;
	edge[tot] = l;
	value[tot] = vv;
	nxt[tot] = head[a];
	head[a] = tot;
}

void out(int x, int y) { // 递归输出
	if (x == 0) {
		cout << "0 ";
		return;
	}
	out(ans[x][y].first, ans[x][y].second);
	cout << x << " ";
}

void dijkstra() {
	for (int i = 0; i < n; i++)
		for (int j = 0; j < 501; j++)
			f[i][j] = 1e9;
	f[0][70] = 0;  // 注意，起点是 0
	// pair<时间，pair<点， 速度>>
	priority_queue<pair<double, pair<int, int >>> q;
	q.push({0, {0, 70} });
	while (q.size()) {
		int u = q.top().second.first;
		int speed = q.top().second.second;
		q.pop();
		if (vis[u][speed]) continue;
		vis[u][speed] = 1;
		// 转移
		for (int i = head[u] ; i ; i = nxt[i]) {
			int v = ver[i];
			// 如果当前点有速度就是当前的速度，如果没有就是上一个的速度
			int ns = value[i] ? value[i] : speed;
			int l = edge[i];
			double time = l * 1.0 / ns;
			if (f[v][ns] > f[u][speed] + time) {
				f[v][ns] = f[u][speed] + time;
				ans[v][ns] = {u, speed};
				q.push({-f[v][ns], {v, ns}});
			}
		}

	}
}

int main() {
	cin >> n >> m >> d;
	for (int i = 1; i <= m; i++) {
		int a, b, v, l;
		cin >> a >> b >> v >> l;
		add(a, b, v, l);
	}

	dijkstra();

	int j = 0;
	// 找最短时间
	for (int i = 0; i < 501; i++)
		if (f[d][i] < f[d][j])
			j = i;
	out(d, j);
	return 0;
}