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

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

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