题目描述

给你 $n$ 个点，$m$ 条无向边，每条边都有长度 $d$ 和花费 $p$，给你起点 $s$ 终点 $t$，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。

输入格式

输入 $n,m$，点的编号是 $1\sim n$，然后是 $m$ 行，每行 $4$ 个数 $a,b,d,p$，表示 $a$ 和 $b$ 之间有一条边，且其长度为 $d$，花费为 $p$。最后一行是两个数 $s,t$；起点 $s$，终点$t$。$n$ 和 $m$ 为 $0$ 时输入结束 $(1<n\leq 1000, 0<m<100000, s != t)$。