题目描述

约翰农场的牛奶输送网络由 $M$ 条管道（$1\le M\le 500$）组成，这些管道用于将牛奶从牛棚输送到牛奶储存罐。他计划在未来一年内移除并更新大部分管道，但希望保留一条完整的管道路径，以便仍能将牛奶从牛棚输送到储存罐。

该管道网络由 $N$ 个连接点（$1\le N\le 500$）描述，每个连接点可以作为一组管道的端点。连接点 $1$ 是牛棚，连接点 $N$ 是储存罐。每条双向管道连接一对连接点，并具有相关的延迟（牛奶从管道一端到达另一端所需的时间）和容量（在稳定状态下每单位时间可以通过管道输送的牛奶量）。同一对连接点之间可以有多条管道连接。

对于从牛棚到储存罐的管道路径，路径的延迟是路径上各管道延迟的总和，路径的容量是路径上各管道容量的最小值（因为这是限制牛奶通过路径的整体速率的「瓶颈」）。如果约翰想通过一条延迟为 $L$、容量为 $C$ 的管道路径输送总量为 $X$ 的牛奶，则所需时间为 $L + X\div C$。

给定约翰的管道网络结构，请帮助他选择一条从牛棚到储存罐的路径，使他能够在最短的总时间内输送 $X$ 单位的牛奶。

输入格式

第 $1$ 行：
三个用空格分隔的整数：$N$ $M$ $X$ 。

第 $2$ 行到第 $M+1$ 行：
每行描述一条管道，包含 $4$ 个整数：$I$ $J$ $L$ $C$。
$I$ 和 $J$ 是管道连接的两个连接点。
$L$ 和 $C$ 分别是管道的延迟和容量。

输出格式

仅有一行、一个整数：
约翰沿着一条路径送牛奶所花费的最少时间（向下取整到最近的整数）。

3 3 15
1 2 10 3
3 2 10 2
1 3 14 1

27

5 7 17
1 2 6 30
2 3 3 17
3 4 20 8
4 5 17 21
1 5 9 29
1 3 3 21
3 5 1 8

6

6 10 24
1 2 11 25
2 3 17 1
3 4 9 26
4 5 16 30
5 6 17 3
3 5 15 27
5 6 23 7
4 6 11 4
2 5 22 21
1 2 19 17

58

数据范围与约定

约翰想通过他的管道网络输送 $15$ 单位的牛奶。管道 $1$ 连接连接点 $1$（牛棚）和连接点 $2$，延迟为 $10$，容量为 $3$。管道 $2$ 和 $3$ 也以类似的方式定义。

路径 $1\to3$ 需要 $14 + 15\div1 = 29$ 单位的时间。路径 $1\to 2\to 3$ 需要 $20 + 15\div2 = 27.5$ 单位的时间，因此是最优的。 （由 ChatGPT 4o 翻译）

($1\le X\le 10^6$)

($1\le I, J\le N$)

($1\le L, C\le 10^6$)