Description

藉由你的協助,喵喵成功決定了旅遊目的地,並且前往「可以玩最久的縣市」。然而,在抵達之後,他發現他之前蒐集到的資料只包含了主要幹道,其實該縣市當中還有更多連接兩相異鄉鎮、錯綜複雜的小路,當然,每一條仍然都是雙向道,而任兩個鄉鎮之間最多只會有一條直接連接的道路(包含幹道和小路)。
更神奇的是,那個縣市的人民,有時候覺得某些路太好走、有時候又覺得太難走。因此,當地政府不時會進行道路施工。
因為道路施工到底要施工得多難走或多好走有些難管控,於是該縣市為每條路定義了一個「好走度」指標。

為了增加民眾滿意度,當地政府調查了人民來往各地的習慣。結果顯示,所有的人民從鄉鎮A到鄉鎮B的路徑,都不會經過相同的路超過一次。然而,由於這個縣市的人口實在是太多了,為了避免塞車或過於擁擠,每個人都會選擇不一樣的路。
因此,該縣市政府處理人民反應路太好走或太難走的方式如下:政府要求人民反應時要提供他路線的起終點,而施工時,他們會把這組起終點之間人民會走的所有可能路線都進行改造,使這些道路的「好走度」全部加或減某個常數。(注意同一次的施工同一條道路的好走度只會被改變一次。)
簡單來說,每次的道路施工都可以表示為三元組(A, B, K),代表把鄉鎮A到鄉鎮B的所有可能路線經過的所有道路「好走度」全部加上K。(K可能是負數。)

正所謂入境隨俗,喵喵到了這個縣市也決定採取「一個旅程不經過相同的路超過一次」的原則。但是由於擔心遇到太難走的道路,所以他事先擬定了一些兩鄉鎮之間的旅程,想要知道每趟旅程中遇到最難走的道路「好走度」最小可以是多少。由於道路實在太多了,而且道路施工實在太常發生了,好走度隨時都會改變,因此你的任務就是幫喵喵寫出一個程式,可以處理該縣市的所有道路施工,並回答喵喵的問題。

Input Format

第一行有一個正整數$T$,代表這筆測試資料是屬於哪個子任務。
第二行有三個正整數$N,M,Q$,分別代表該縣市的鄉鎮數量、雙向道數量、道路施工與詢問的總量。
接下來$M$行,每行有三個非負整數$A,B,K$,代表有一條雙向道連接鄉鎮$A,B$,其「好走度」為$K$。
接下來$Q$行,每行代表一個道路施工或一個詢問:
如果是0 A B K,代表道路施工,表示為三元組(A, B, K)。詳細說明請見題目敘述。
如果是1 A B,代表詢問所有從鄉鎮A到鄉鎮B的走法中,遇到最難走的道路「好走度」的最小值。

對於所有測資,$N,M\leq 10^ 5$,$Q\leq 8\times 10^ 4$。
保證所有道路、道路施工或詢問指定的鄉鎮都存在,且詢問或操作的兩鄉鎮必相異。
對於任何時刻任何一條道路的「好走度」K,$|K|\leq 10^ 8$。

子任務(測資) 額外限制 分數
1 (0~2) $N, M, Q\leq 8$ 17
2 (0~5) $N, Q\leq 2000$ 46
3 (6~8) 不會有道路施工 11
4 (9~11) 至少存在一種方法,可以從鄉鎮0開始恰經過所有幹道和小路一次後回到鄉鎮0(當然會重複經過鄉鎮) 13
5 (12~14) 只有幹道,沒有小路 47
6 (0~17) 無限制 66

Output Format

對於每一筆詢問,輸出一行整數代表所要求的答案。

Sample Input 1

1
3 3 4
0 1 5
1 2 7
2 0 11
0 1 2 -5
1 0 2
0 0 1 10
1 1 2

Sample Output 1

2
12

Hints

時間寶貴,好吃的小測資記得拿(?

Problem Source

Problem set / Description by Yihda Yol
建國中學105學年度校內第四次模擬賽pF

Subtasks

No. Testdata Range Score
1 0~2 17
2 0~5 46
3 6~8 11
4 9~11 13
5 12~14 47
6 0~17 66

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 900 131072 262144 1 2 6
1 900 131072 262144 1 2 6
2 900 131072 262144 1 2 6
3 900 131072 262144 2 6
4 900 131072 262144 2 6
5 900 131072 262144 2 6
6 900 131072 262144 3 6
7 900 131072 262144 3 6
8 900 131072 262144 3 6
9 900 131072 262144 4 6
10 900 131072 262144 4 6
11 900 131072 262144 4 6
12 900 131072 262144 5 6
13 900 131072 262144 5 6
14 900 131072 262144 5 6
15 900 131072 262144 6
16 900 131072 262144 6
17 900 131072 262144 6