{"problem":{"name":"G. Short Path","description":{"content":"In my opinion, people are divided into two categories: some live in the future while others — in the past. Should it be explained what category did I belong? The mystery I hunted for a half of my life","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10081G"},"statements":[{"statement_type":"Markdown","content":"In my opinion, people are divided into two categories: some live in the future while others — in the past. Should it be explained what category did I belong? The mystery I hunted for a half of my life, finally was taking shape. Good Magician didn't know where Dragon hid. But he knew that bandit dens in some cities of the kingdom were controlled by people from the Dragon's gang. For each city he gave me a reliable information, whether Dragon controlled that city or not.\n\nI was staring on the map of Fairy Kingdom trying to understand where to go now. There were n cities in the Kingdom, connected by m roads, with the length of the j-th road equal to wj. I guessed that Dragon hid in one of two cities controlled by his gang with the shortest path between them. First of all, the traffic of Blue Tea was the highest between them, and secondly, in case of emergency it was possible to move quickly from one of the cities to the other. All that remained was just to find such pair of cities.\n\nThe first line contains two integers separated by a space: n and m (2 ≤ n ≤ 105, 1 ≤ m ≤ 105) — the number of cities in Fairy Kingdom and the number of roads between them, correspondingly.\n\nThe second line contains n integers separated by spaces. On the i-th position the number 1 is written, if the i-th city is under control of Dragon's gang; otherwise the number 0 is written there.\n\nThe next m lines contain three integers each, separated by spaces: ai, bi, wi (1 ≤ ai < bi ≤ n, 1 ≤ wi ≤ 109) — the numbers of cities connected by a road and the length of this road. The cities are numbered from 1. Each pair of cities is presented at most once.\n\nIn the first line output a single integer — the length of the shortest path between cities where Dragon presumably hides.\n\nIn the second line output two integers separated by a space — the numbers of these cities.\n\nIf there are several possible answers, output any of them. If no two cities controlled by Dragon's people have a path between them, output «_No luck at all_» without quotes.\n\n## Input\n\nThe first line contains two integers separated by a space: n and m (2 ≤ n ≤ 105, 1 ≤ m ≤ 105) — the number of cities in Fairy Kingdom and the number of roads between them, correspondingly.The second line contains n integers separated by spaces. On the i-th position the number 1 is written, if the i-th city is under control of Dragon's gang; otherwise the number 0 is written there.The next m lines contain three integers each, separated by spaces: ai, bi, wi (1 ≤ ai < bi ≤ n, 1 ≤ wi ≤ 109) — the numbers of cities connected by a road and the length of this road. The cities are numbered from 1. Each pair of cities is presented at most once.\n\n## Output\n\nIn the first line output a single integer — the length of the shortest path between cities where Dragon presumably hides.In the second line output two integers separated by a space — the numbers of these cities.If there are several possible answers, output any of them. If no two cities controlled by Dragon's people have a path between them, output «_No luck at all_» without quotes.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ t \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ N \\in \\mathbb{Z} $ be the number of cities, $ M \\in \\mathbb{Z} $ the number of roads, $ K \\in \\mathbb{Z} $ the maximum allowed total cost.  \n- Let $ G = (V, E) $ be a directed graph where $ V = \\{1, 2, \\dots, N\\} $, and each edge $ e \\in E $ is a tuple $ (s_1, s_2, c, W) $, representing a road from city $ s_1 $ to city $ s_2 $ with cost $ c $ and minimum required wisdom $ W $.  \n\n**Constraints**  \n1. $ 1 \\le t \\le \\text{large} $  \n2. $ 1 < N \\le 10^5 $, $ 1 \\le M \\le 10^5 $, $ 1 \\le K \\le 10^9 $  \n3. For each road: $ 1 \\le s_1, s_2 \\le N $, $ 1 \\le c \\le 10^9 $, $ 1 \\le W \\le 10^9 $  \n\n**Objective**  \nFind the minimum wisdom value $ W_{\\min} $ such that there exists a path from city $ 1 $ to city $ N $ using only roads with $ W \\le W_{\\min} $, and the total cost of the path is strictly less than $ K $.  \nIf no such path exists, output $ -1 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10081G","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}