Consider car trips in a country where there is no friction. Cars in this country do not have engines. Once a car started to move at a speed, it keeps moving at the same speed. There are acceleration devices on some points on the road, where a car can increase or decrease its speed by 1. It can also keep its speed there. Your job in this problem is to write a program which determines the route with the shortest time to travel from a starting city to a goal city.

There are several cities in the country, and a road network connecting them. Each city has an acceleration device. As mentioned above, if a car arrives at a city at a speed v , it leaves the city at one of v - 1, v , or v + 1. The first road leaving the starting city must be run at the speed 1. Similarly, the last road arriving at the goal city must be run at the speed 1.

The starting city and the goal city are given. The problem is to find the best route which leads to the goal city going through several cities on the road network. When the car arrives at a city, it cannot immediately go back the road it used to reach the city. No U-turns are allowed. Except this constraint, one can choose any route on the road network. It is allowed to visit the same city or use the same road multiple times. The starting city and the goal city may be visited during the trip.

For each road on the network, its distance and speed limit are given. A car must run a road at a speed less than or equal to its speed limit. The time needed to run a road is the distance divided by the speed. The time needed within cities including that for acceleration or deceleration should be ignored.

Input

The input consists of multiple datasets, each in the following format.

> n  m
>  s  g
>  x 1 y 1 d 1 c 1
>  ...
>  xm ym dm cm
>

Every input item in a dataset is a non-negative integer. Input items in the same line are separated by a space.

The first line gives the size of the road network. n  is the number of cities in the network. You can assume that the number of cities is between 2 and 30, inclusive. m  is the number of roads between cities, which may be zero.

The second line gives the trip. s  is the city index of the starting city. g  is the city index of the goal city. s  is not equal to g . You can assume that all city indices in a dataset (including the above two) are between 1 and n , inclusive.

The following m  lines give the details of roads between cities. The i -th road connects two cities with city indices xi and yi , and has a distance di (1 ≤ i ≤ m ). You can assume that the distance is between 1 and 100, inclusive. The speed limit of the road is specified by ci . You can assume that the speed limit is between 1 and 30, inclusive.

No two roads connect the same pair of cities. A road never connects a city with itself. Each road can be traveled in both directions.

The last dataset is followed by a line containing two zeros (separated by a space).

Output

For each dataset in the input, one line should be output as specified below. An output line should not contain extra characters such as spaces.

If one can travel from the starting city to the goal city, the time needed for the best route (a route with the shortest time) should be printed. The answer should not have an error greater than 0.001. You may output any number of digits after the decimal point, provided that the above accuracy condition is satisfied.

If it is impossible to reach the goal city, the string "`unreachable`" should be printed. Note that all the letters of "`unreachable`" are in lowercase.

Sample Input


2 0
1 2
5 4
1 5
1 2 1 1
2 3 2 2
3 4 2 2
4 5 1 1
6 6
1 6
1 2 2 1
2 3 2 1
3 6 2 1
1 4 2 30
4 5 3 30
5 6 2 30
6 7
1 6
1 2 1 30
2 3 1 30
3 1 1 30
3 4 100 30
4 5 1 30
5 6 1 30
6 4 1 30
0 0


Output for the Sample Input


unreachable
4.00000
5.50000
11.25664






Example

Input

2 0
1 2
5 4
1 5
1 2 1 1
2 3 2 2
3 4 2 2
4 5 1 1
6 6
1 6
1 2 2 1
2 3 2 1
3 6 2 1
1 4 2 30
4 5 3 30
5 6 2 30
6 7
1 6
1 2 1 30
2 3 1 30
3 1 1 30
3 4 100 30
4 5 1 30
5 6 1 30
6 4 1 30
0 0


Output

unreachable
4.00000
5.50000
11.25664

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
from collections import defaultdict
from heapq import heappop, heappush
while True:
	(n, m) = map(int, input().split())
	if n == 0 and m == 0:
		break
	(s, g) = map(int, input().split())
	graph = defaultdict(list)
	for _ in range(m):
		(x, y, d, c) = map(int, input().split())
		graph[x].append((y, d, c))
		graph[y].append((x, d, c))

	def dijkstra(s):
		d = defaultdict(lambda : float('INF'))
		d[s, 0, -1] = 0
		used = defaultdict(bool)
		q = []
		heappush(q, (0, (s, 0, -1)))
		while len(q):
			(elapsed, v) = heappop(q)
			(cur, vel1, prev1) = (v[0], v[1], v[2])
			if cur == g and vel1 == 1:
				return elapsed
			if used[v]:
				continue
			used[v] = True
			for (to, dist, ct) in graph[cur]:
				if to == prev1:
					continue
				for vel2 in range(vel1 - 1, vel1 + 2):
					if vel2 < 1 or ct < vel2:
						continue
					nxt = (to, vel2, cur)
					if used[nxt]:
						continue
					elapsed2 = elapsed + dist / vel2
					if d[nxt] > elapsed2:
						d[nxt] = elapsed2
						heappush(q, (elapsed2, nxt))
		return 'unreachable'
	print(dijkstra(s))


def solve():
	import sys
	from heapq import heappush, heappop
	file_input = sys.stdin
	inf = float('inf')
	while True:
		(n, m) = map(int, file_input.readline().split())
		if n == 0:
			break
		(s, g) = map(int, file_input.readline().split())
		adj_list = [[] for i in range(n)]
		for i in range(m):
			(x, y, d, c) = map(int, file_input.readline().split())
			x -= 1
			y -= 1
			adj_list[x].append((y, d, c))
			adj_list[y].append((x, d, c))
		s -= 1
		g -= 1
		time_rec = [[[inf] * 31 for j in range(n)] for i in range(n)]
		time_rec[s][s][1] = 0
		pq = [(0, s, s, 0)]
		while pq:
			(t, c, p, s) = heappop(pq)
			if time_rec[p][c][s] < t:
				continue
			if c == g and s == 1:
				print(t)
				break
			for (next_city, d, s_limit) in adj_list[c]:
				if next_city == p:
					continue
				if s <= 1:
					lower_limit = 1
				else:
					lower_limit = s - 1
				for shifted_s in range(lower_limit, s + 2):
					if shifted_s > s_limit:
						continue
					next_t = t + d / shifted_s
					if time_rec[c][next_city][shifted_s] <= next_t:
						continue
					else:
						heappush(pq, (next_t, next_city, c, shifted_s))
						time_rec[c][next_city][shifted_s] = next_t
		else:
			print('unreachable')
solve()


import sys
from heapq import heappop, heappush
from collections import defaultdict

def solve(n, m):
	(s, g) = [int(x) for x in sys.stdin.readline().split()]
	s -= 1
	g -= 1
	e = [[] for i in range(n)]
	for i in range(m):
		(a, b, d, c) = [int(x) for x in sys.stdin.readline().split()]
		a -= 1
		b -= 1
		e[a].append((b, d, c))
		e[b].append((a, d, c))
	dist = defaultdict(lambda : float('inf'))
	dist[s, 0, -1] = 0
	q = [(0, s, 0, -1)]
	while q:
		(dx, x, v, p) = heappop(q)
		if x == g and v == 1:
			print(dx)
			return
		for i in range(-1, 2):
			v_ = v + i
			if v_ < 1:
				continue
			for (y, d, c) in e[x]:
				if p == y:
					continue
				if v_ > c:
					continue
				z = d / v_
				if dx + z < dist[y, v_, x]:
					dist[y, v_, x] = dx + z
					heappush(q, (dist[y, v_, x], y, v_, x))
	print('unreachable')
	return
while 1:
	(n, m) = [int(x) for x in sys.stdin.readline().split()]
	if n == 0:
		break
	solve(n, m)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def main():
	rr = []
	while True:
		(n, m) = LI()
		if n == 0:
			break
		(s, g) = LI()
		a = [LI() for _ in range(m)]
		e = collections.defaultdict(list)
		for (x, y, d, c) in a:
			e[x].append((y, d, c))
			e[y].append((x, d, c))

		def search(s):
			d = collections.defaultdict(lambda : inf)
			d[s, 0, -1] = 0
			q = []
			heapq.heappush(q, (0, (s, 0, -1)))
			v = collections.defaultdict(bool)
			while len(q):
				(k, u) = heapq.heappop(q)
				if v[u]:
					continue
				v[u] = True
				if u[0] == g and u[1] == 1:
					return '{:0.9f}'.format(k)
				c = u[1]
				b = u[2]
				for (uv, ud, uc) in e[u[0]]:
					if uv == b:
						continue
					for tc in range(max(c - 1, 1), min(uc + 1, c + 2)):
						nuv = (uv, tc, u[0])
						if v[nuv]:
							continue
						vd = k + ud / tc
						if d[nuv] > vd:
							d[nuv] = vd
							heapq.heappush(q, (vd, nuv))
			return 'unreachable'
		rr.append(search(s))
	return '\n'.join(map(str, rr))
print(main())


import sys
import heapq
if sys.version[0] == '2':
	(range, input) = (xrange, raw_input)
MAX_SPEED = 30
dvs = (-1, 0, 1)
while True:
	(N, M) = map(int, input().split())
	if not N | M:
		break
	(S, G) = map(lambda x: int(x) - 1, input().split())
	edge = [[] for _ in range(N)]
	for _ in range(M):
		(x, y, d, c) = map(int, input().split())
		edge[x - 1].append((y - 1, d, c))
		edge[y - 1].append((x - 1, d, c))
	INF = 1000000000.0
	dist = [[[INF for _ in range(N)] for _ in range(MAX_SPEED + 1)] for _ in range(N)]
	que = [(0.0, S, 0, S)]
	while que:
		(cost, now, v, prev) = heapq.heappop(que)
		if cost > dist[now][v][prev]:
			continue
		if now == G and v == 1:
			print('{:.20f}'.format(cost))
			break
		dist[now][v][prev] = cost
		for (x, d, c) in edge[now]:
			if x == prev:
				continue
			for dv in dvs:
				nv = v + dv
				if 0 < nv <= c and dist[x][nv][now] > dist[now][v][prev] + d / nv:
					dist[x][nv][now] = dist[now][v][prev] + d / nv
					heapq.heappush(que, (dist[x][nv][now], x, nv, now))
	else:
		print('unreachable')


from collections import deque
from heapq import heappop, heappush

def inpl():
	return list(map(int, input().split()))
INF = 50000
(N, M) = inpl()
while N:
	(s, g) = inpl()
	G = [[] for _ in range(N + 1)]
	for _ in range(M):
		(a, b, d, c) = inpl()
		G[a].append([b, c, d])
		G[b].append([a, c, d])
	DP = [[[INF] * (N + 1) for _ in range(31)] for _ in range(N + 1)]
	DP[s][0][0] = 0
	Q = [[0, 0, s, 0]]
	while Q:
		(t, v, p, bp) = heappop(Q)
		if DP[p][v][bp] < t:
			continue
		for (q, c, d) in G[p]:
			if q == bp:
				continue
			for dv in range(-1, 2):
				nv = v + dv
				if not 0 < nv <= c:
					continue
				nt = t + d / nv
				if DP[q][nv][p] > nt:
					DP[q][nv][p] = nt
					heappush(Q, [nt, nv, q, p])
	ans = min(DP[g][1])
	if ans == INF:
		print('unreachable')
	else:
		print(ans)
	(N, M) = inpl()


INF = 1000000000.0
import heapq

def dijkstra(V, to, start, goal):
	node = [[[INF for k in range(31)] for j in range(V)] for i in range(V)]
	Q = []
	node[start][0][0] = 0
	heapq.heappush(Q, (0, start, -1, 0))
	while Q:
		(t, s, p, v) = heapq.heappop(Q)
		if s == goal and v == 1:
			return t
		for (e, d, c) in to[s]:
			if e == p:
				continue
			for i in range(-1, 2):
				nv = v + i
				if nv > c or nv <= 0:
					continue
				nt = t + d / nv
				if nt < node[e][s][nv]:
					node[e][s][nv] = nt
					heapq.heappush(Q, (nt, e, s, nv))
	return -1
while True:
	(n, m) = map(int, input().split())
	if n == 0:
		break
	(s, g) = map(int, input().split())
	s -= 1
	g -= 1
	to = [[] for i in range(n)]
	for i in range(m):
		(x, y, d, c) = map(int, input().split())
		x -= 1
		y -= 1
		to[x].append((y, d, c))
		to[y].append((x, d, c))
	ans = dijkstra(n, to, s, g)
	print(ans if ans >= 0 else 'unreachable')


import sys
import heapq
if sys.version[0] == '2':
	(range, input) = (xrange, raw_input)
MAX_SPEED = 30
while True:
	(N, M) = map(int, input().split())
	if not N | M:
		break
	(S, G) = map(lambda x: int(x) - 1, input().split())
	edge = [[] for _ in range(N)]
	for _ in range(M):
		(x, y, d, c) = map(int, input().split())
		edge[x - 1].append((y - 1, d, c))
		edge[y - 1].append((x - 1, d, c))
	INF = float('inf')
	dist = [[[INF for _ in range(N)] for _ in range(MAX_SPEED + 1)] for _ in range(N)]
	que = [(0.0, S, 0, S)]
	while que:
		(cost, now, v, prev) = heapq.heappop(que)
		if cost > dist[now][v][prev]:
			continue
		if now == G and v == 1:
			print('{:.20f}'.format(cost))
			break
		dist[now][v][prev] = cost
		for (x, d, c) in edge[now]:
			if x == prev:
				continue
			for dv in (-1, 0, 1):
				nv = v + dv
				if 0 < nv <= c and dist[x][nv][now] > dist[now][v][prev] + d / nv:
					dist[x][nv][now] = dist[now][v][prev] + d / nv
					heapq.heappush(que, (dist[x][nv][now], x, nv, now))
	else:
		print('unreachable')


import sys
import heapq
if sys.version[0] == '2':
	(range, input) = (xrange, raw_input)
MAX_SPEED = 30
while True:
	(N, M) = map(int, input().split())
	if not N | M:
		break
	(S, G) = map(lambda x: int(x) - 1, input().split())
	edge = [[] for _ in range(N)]
	for _ in range(M):
		(x, y, d, c) = map(int, input().split())
		edge[x - 1].append((y - 1, d, c))
		edge[y - 1].append((x - 1, d, c))
	INF = 1e+18
	dist = [[[INF for _ in range(N)] for _ in range(MAX_SPEED + 1)] for _ in range(N)]
	que = [(0.0, S, 0, S)]
	while que:
		(cost, now, v, prev) = heapq.heappop(que)
		if cost > dist[now][v][prev]:
			continue
		if now == G and v == 1:
			print('{:.20f}'.format(cost))
			break
		dist[now][v][prev] = cost
		for (x, d, c) in edge[now]:
			if x == prev:
				continue
			for dv in (-1, 0, 1):
				nv = v + dv
				if 0 < nv <= c and dist[x][nv][now] > dist[now][v][prev] + d / nv:
					dist[x][nv][now] = dist[now][v][prev] + d / nv
					heapq.heappush(que, (dist[x][nv][now], x, nv, now))
	else:
		print('unreachable')


import sys
import heapq
if sys.version[0] == '2':
	(range, input) = (xrange, raw_input)
MAX_SPEED = 30
while True:
	(N, M) = map(int, input().split())
	if not N | M:
		break
	(S, G) = map(lambda x: int(x) - 1, input().split())
	edge = [[] for _ in range(N)]
	for _ in range(M):
		(x, y, d, c) = map(int, input().split())
		edge[x - 1].append((y - 1, d, c))
		edge[y - 1].append((x - 1, d, c))
	INF = float('inf')
	dist = [[[INF for _ in range(N)] for _ in range(MAX_SPEED + 1)] for _ in range(N)]
	que = [(0.0, S, 0, S)]
	while que:
		(cost, now, v, prev) = heapq.heappop(que)
		if cost > dist[now][v][prev]:
			continue
		if now == G and v == 1:
			print('{:.20f}'.format(cost))
			break
		dist[now][v][prev] = cost
		for (x, d, c) in edge[now]:
			if x == prev:
				continue
			if 0 < v <= c and dist[x][v][now] > dist[now][v][prev] + d / v:
				dist[x][v][now] = dist[now][v][prev] + d / v
				heapq.heappush(que, (dist[x][v][now], x, v, now))
			if v < c and dist[x][v + 1][now] > dist[now][v][prev] + d / (v + 1):
				dist[x][v + 1][now] = dist[now][v][prev] + d / (v + 1)
				heapq.heappush(que, (dist[x][v + 1][now], x, v + 1, now))
			if 1 < v <= c + 1 and dist[x][v - 1][now] > dist[now][v][prev] + d / (v - 1):
				dist[x][v - 1][now] = dist[now][v][prev] + d / (v - 1)
				heapq.heappush(que, (dist[x][v - 1][now], x, v - 1, now))
	else:
		print('unreachable')


from heapq import heappush, heappop

def main():
	while True:
		(n, m) = map(int, input().split())
		if n == 0:
			break
		(s, g) = map(int, input().split())
		s -= 1
		g -= 1
		edges = [[] for _ in range(n)]
		for _ in range(m):
			(x, y, d, c) = map(int, input().split())
			x -= 1
			y -= 1
			edges[x].append((y, d, c))
			edges[y].append((x, d, c))
		que = []
		heappush(que, (0, 1, s, None))
		dic = {}
		dic[1, None, s, None] = 0
		INF = 10 ** 20
		ans = INF
		while que:
			(score, speed, node, pre_node) = heappop(que)
			if score >= ans:
				break
			for (to, dist, limit) in edges[node]:
				if to == pre_node or speed > limit:
					continue
				new_score = score + dist / speed
				if speed == 1 and to == g and (ans > new_score):
					ans = new_score
				for new_speed in (speed - 1, speed, speed + 1):
					if new_speed <= 0:
						continue
					if (new_speed, to, node) not in dic or dic[new_speed, to, node] > new_score:
						dic[new_speed, to, node] = new_score
						heappush(que, (new_score, new_speed, to, node))
		if ans == INF:
			print('unreachable')
		else:
			print(ans)
main()