There are a lot of problems related to the shortest paths. Nevertheless, there are not much problems, related to the shortest paths in average.
Consider a directed graph G, consisting of N nodes and M edges. Consider a walk from the node A to the node B in this graph. The average length of this walk will be total sum of weight of its' edges divided by number of edges. Every edge counts as many times as it appears in this path.
Now, your problem is quite simple. For the given graph and two given nodes, find out the shortest average length of the walk between these nodes. Please note, that the length of the walk need not to be finite, but average walk length will be.

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a pair of space-separated integers N and M denoting the number of nodes and the number of edges in the graph.
Each of the following M lines contains a triple of space-separated integers Xi Yi Zi, denoting the arc, connecting the node Xi to the node Yi (but not vice-versa!) having the weight of Zi.
The next line contains a pair of space separated integers A and B, denoting the first and the last node of the path.

-----Output-----
For each test case, output a single line containing the length of the shortest path in average.
If there is no path at all, output just -1 on the corresponding line of the output.

-----Constraints-----
- 1 ≤ N ≤ 500
- 1 ≤ M ≤ 1000
- A is not equal to B
- 1 ≤ A, B, Xi, Yi ≤ N
- 1 ≤ Zi ≤ 100
- There are no self-loops and multiple edges in the graph.
- 1 ≤ sum of N over all test cases ≤ 10000
- 1 ≤ sum of M over all test cases ≤ 20000

-----Subtasks-----
- Subtask #1 (45 points): 1 ≤ N ≤ 10, 1 ≤ M ≤ 20; Your answer will be considered correct in case it has an absolute or relative error of no more than 10-2.
- Subtask #2 (55 points): no additional constraints; Your answer will be considered correct in case it has an absolute or relative error of no more than 10-6.

-----Example-----
Input:2
3 3
1 2 1
2 3 2
3 2 3
1 3
3 3
1 2 10
2 3 1
3 2 1
1 3

Output:1.5
1.0

-----Explanation-----
Example case 1. The walk 1 -> 2 and 2 -> 3 has average length of 3/2 = 1.5. Any other walks in the graph will have more or equal average length than this.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'from collections import defaultdict\nimport copy\n#def dfs(l,r,dct):\ndef dfs(l,r,dct):\n visit=[0 for i in range(n+1)]\n arr=[l]\n while(arr):\n  node=arr.pop()\n  if node==r:return True\n  visit[node]=1\n  for lnk in dct[node]:\n   if not visit[lnk]:\n    arr.append(lnk)\n return False\n \ndef ok(mid,cst):\n for i,j in edges:\n  cst[i][j]-=mid\n \n d=[10**9]*(n+1)\n d[l]=0\n for _ in range(n-1):\n  for i,j in edges:\n   d[j]=min(d[j],d[i]+cst[i][j])\n   \n if d[r]<=0:return 1\n for i,j in edges:\n  if d[j]>d[i]+cst[i][j] and dfs(l,i,dct) and dfs(j,r,dct):\n   return 1\n return 0\n \nfor _ in range(int(input())):\n n,m=map(int,input().split())\n dct=defaultdict(list)\n \n cost=[[1000 for i in range(n+1)] for j in range(n+1)]\n edges=[]\n for i in range(m):\n  a,b,w=map(int,input().split())\n  edges.append([a,b])\n  dct[a].append(b)\n  cost[a][b]=min(cost[a][b],w)\n \n l,r=map(int,input().split())\n if not dfs(l,r,dct):\n  print(-1)\n  continue\n #print(cost)\n lo=1\n hi=101\n for i in range(100):\n  cst=copy.deepcopy(cost)\n  mid=(lo+hi)/2\n  if ok(mid,cst):hi=mid-1\n  else:lo=mid+1\n print("%.7f"%mid)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 178439