题目背景

在遥远的未来，人类已经迈入了星际文明的时代。为了更高效地管理庞大的星际网络，星际联盟决定建立一个全新的通信系统。你被任命为首席网络构建者，负责设计这个系统的连接方式。你的任务是通过一系列的连接操作，确保从主控星球出发，能够以最短的路径到达每一个星球。为了评估你的设计效率，联盟要求你计算一个特定的指标。现在，就让我们开始这项星际级的挑战吧！

题目描述

你需要通过 $m$ 次连接操作，构建一个包含 $n$ 个星球的无向通信网络。每次连接操作由五元组 $(a_i,b_i,c_i,d_i,w_i)$ 表示，表示对所有 $x \in [a_i,b_i]$ 和 $y \in [c_i,d_i]$，添加一条长度为 $w_i$ 的边 $(x,y)$。请注意，可能存在 $x = y$ 的情况。

你的目标是从主控星球 $fin$ 出发，计算到每个星球的最短路径长度。为了简化输出，只需计算并输出 $\sum_{i=1}^n dis(fin,i) \times i$ 的值，其中 $dis(i,j)$ 表示从星球 $i$ 到星球 $j$ 的最短路径长度。保证构建后的网络是连通的。

输入格式

第一行包含三个整数 $n, m, fin$。接下来的 $m$ 行，每行包含五个整数 $a_i, b_i, c_i, d_i, w_i$，表示一次连接操作。

输出格式

输出一个整数，表示 $\sum_{i=1}^n dis(fin,i) \times i$ 的值，保证答案不超过 $64$ 位整数。

4 3 3
1 2 3 4 3
1 3 2 4 2
2 3 1 4 2

14

说明/提示

保证 $1 \leq n \leq 3 \times 10^5,1 \leq m \leq 10^5,1 \leq a_i \leq b_i \leq n,1 \leq c_i \leq d_i \leq n,1 \leq w_i \leq 10^7$。