{"raw_statement":[{"iden":"problem statement","content":"There are $N$ cities numbered $1$ to $N$, connected by $M$ railroads.\nYou are now at City $1$, with $10^{100}$ gold coins and $S$ silver coins in your pocket.\nThe $i$\\-th railroad connects City $U_i$ and City $V_i$ bidirectionally, and a one-way trip costs $A_i$ silver coins and takes $B_i$ minutes. You cannot use gold coins to pay the fare.\nThere is an exchange counter in each city. At the exchange counter in City $i$, you can get $C_i$ silver coins for $1$ gold coin. The transaction takes $D_i$ minutes for each gold coin you give. You can exchange any number of gold coins at each exchange counter.\nFor each $t=2, ..., N$, find the minimum time needed to travel from City $1$ to City $t$. You can ignore the time spent waiting for trains."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 50$\n*   $N-1 \\leq M \\leq 100$\n*   $0 \\leq S \\leq 10^9$\n*   $1 \\leq A_i \\leq 50$\n*   $1 \\leq B_i,C_i,D_i \\leq 10^9$\n*   $1 \\leq U_i < V_i \\leq N$\n*   There is no pair $i, j(i \\neq j)$ such that $(U_i,V_i)=(U_j,V_j)$.\n*   Each city $t=2,...,N$ can be reached from City $1$ with some number of railroads.\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$ $S$\n$U_1$ $V_1$ $A_1$ $B_1$\n$:$\n$U_M$ $V_M$ $A_M$ $B_M$\n$C_1$ $D_1$\n$:$\n$C_N$ $D_N$"},{"iden":"sample input 1","content":"3 2 1\n1 2 1 2\n1 3 2 4\n1 11\n1 2\n2 5"},{"iden":"sample output 1","content":"2\n14\n\nThe railway network in this input is shown in the figure below.\nIn this figure, each city is labeled as follows:\n\n*   The first line: the ID number $i$ of the city ($i$ for City $i$)\n*   The second line: $C_i$ / $D_i$\n\nSimilarly, each railroad is labeled as follows:\n\n*   The first line: the ID number $i$ of the railroad ($i$ for the $i$\\-th railroad in input)\n*   The second line: $A_i$ / $B_i$\n\n![image](https://img.atcoder.jp/ghi/83f6a1d296d017f40372ea1e1d3b26e5.png)\nYou can travel from City $1$ to City $2$ in $2$ minutes, as follows:\n\n*   Use the $1$\\-st railroad to move from City $1$ to City $2$ in $2$ minutes.\n\n  \n\nYou can travel from City $1$ to City $3$ in $14$ minutes, as follows:\n\n*   Use the $1$\\-st railroad to move from City $1$ to City $2$ in $2$ minutes.\n*   At the exchange counter in City $2$, exchange $3$ gold coins for $3$ silver coins in $6$ minutes.\n*   Use the $1$\\-st railroad to move from City $2$ to City $1$ in $2$ minutes.\n*   Use the $2$\\-nd railroad to move from City $1$ to City $3$ in $4$ minutes."},{"iden":"sample input 2","content":"4 4 1\n1 2 1 5\n1 3 4 4\n2 4 2 2\n3 4 1 1\n3 1\n3 1\n5 2\n6 4"},{"iden":"sample output 2","content":"5\n5\n7\n\nThe railway network in this input is shown in the figure below:\n![image](https://img.atcoder.jp/ghi/a081a72c42da7902a30f29f981c368d0.png)\nYou can travel from City $1$ to City $4$ in $7$ minutes, as follows:\n\n*   At the exchange counter in City $1$, exchange $2$ gold coins for $6$ silver coins in $2$ minutes.\n*   Use the $2$\\-nd railroad to move from City $1$ to City $3$ in $4$ minutes.\n*   Use the $4$\\-th railroad to move from City $3$ to City $4$ in $1$ minutes."},{"iden":"sample input 3","content":"6 5 1\n1 2 1 1\n1 3 2 1\n2 4 5 1\n3 5 11 1\n1 6 50 1\n1 10000\n1 3000\n1 700\n1 100\n1 1\n100 1"},{"iden":"sample output 3","content":"1\n9003\n14606\n16510\n16576\n\nThe railway network in this input is shown in the figure below:\n![image](https://img.atcoder.jp/ghi/c61c66a7977129c9ef86c6770b37acba.png)\nYou can travel from City $1$ to City $6$ in $16576$ minutes, as follows:\n\n*   Use the $1$\\-st railroad to move from City $1$ to City $2$ in $1$ minute.\n*   At the exchange counter in City $2$, exchange $3$ gold coins for $3$ silver coins in $9000$ minutes.\n*   Use the $1$\\-st railroad to move from City $2$ to City $1$ in $1$ minute.\n*   Use the $2$\\-nd railroad to move from City $1$ to City $3$ in $1$ minute.\n*   At the exchange counter in City $3$, exchange $8$ gold coins for $8$ silver coins in $5600$ minutes.\n*   Use the $2$\\-nd railroad to move from City $3$ to City $1$ in $1$ minute.\n*   Use the $1$\\-st railroad to move from City $1$ to City $2$ in $1$ minute.\n*   Use the $3$\\-rd railroad to move from City $2$ to City $4$ in $1$ minute.\n*   At the exchange counter in City $4$, exchange $19$ gold coins for $19$ silver coins in $1900$ minutes.\n*   Use the $3$\\-rd railroad to move from City $4$ to City $2$ in $1$ minute.\n*   Use the $1$\\-st railroad to move from City $2$ to City $1$ in $1$ minute.\n*   Use the $2$\\-nd railroad to move from City $1$ to City $3$ in $1$ minute.\n*   Use the $4$\\-th railroad to move from City $3$ to City $5$ in $1$ minute.\n*   At the exchange counter in City $5$, exchange $63$ gold coins for $63$ silver coins in $63$ minutes.\n*   Use the $4$\\-th railroad to move from City $5$ to City $3$ in $1$ minute.\n*   Use the $2$\\-nd railroad to move from City $3$ to City $1$ in $1$ minute.\n*   Use the $5$\\-th railroad to move from City $1$ to City $6$ in $1$ minute."},{"iden":"sample input 4","content":"4 6 1000000000\n1 2 50 1\n1 3 50 5\n1 4 50 7\n2 3 50 2\n2 4 50 4\n3 4 50 3\n10 2\n4 4\n5 5\n7 7"},{"iden":"sample output 4","content":"1\n3\n5\n\nThe railway network in this input is shown in the figure below:\n![image](https://img.atcoder.jp/ghi/bfbde2d55baea1e0487f80a62ef9b4ab.png)"},{"iden":"sample input 5","content":"2 1 0\n1 2 1 1\n1 1000000000\n1 1"},{"iden":"sample output 5","content":"1000000001\n\nThe railway network in this input is shown in the figure below:\n![image](https://img.atcoder.jp/ghi/16b8d5c94640ed5b38c0863716196890.png)\nYou can travel from City $1$ to City $2$ in $1000000001$ minutes, as follows:\n\n*   At the exchange counter in City $1$, exchange $1$ gold coin for $1$ silver coin in $1000000000$ minutes.\n*   Use the $1$\\-st railroad to move from City $1$ to City $2$ in $1$ minute."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}