{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"MD","content":"Bạn được cho một đồ thị vô hướng có trọng số trên n đỉnh và m cạnh. Tìm đường đi ngắn nhất từ đỉnh s đến đỉnh t hoặc thông báo rằng không tồn tại đường đi như vậy.\n\nĐầu vào\nDòng đầu tiên của đầu vào chứa hai số nguyên được phân tách bằng khoảng trắng - n và m (1 ≤ n ≤ 10^5; 0 ≤ m ≤ 10^5).\n\nTiếp theo, m dòng chứa mô tả về các cạnh của đồ thị. Dòng thứ i chứa ba số nguyên được phân tách bằng khoảng trắng - ui, vi, xi (1 ≤ ui, vi ≤ n; 0 ≤ xi ≤ 10^5). Điều đó có nghĩa là các đỉnh có số ui và vi được kết nối bởi cạnh có độ dài 2^xi (2 mũ xi).\n\nDòng cuối cùng chứa hai số nguyên được phân tách bằng khoảng trắng - số của các đỉnh s và t.\n\nCác đỉnh được đánh số từ 1 đến n. Đồ thị không chứa cạnh lặp và khuyên.\n\nĐầu ra\nTrong dòng đầu tiên, in phần dư sau khi mod độ dài đường đi ngắn nhất cho 1000000007 (10^9 + 7) nếu tồn tại đường đi, và -1 nếu không tồn tại đường đi.\n\nNếu tồn tại đường đi, in trong dòng thứ hai số nguyên k - số lượng đỉnh trên đường đi ngắn nhất từ đỉnh s đến đỉnh t; trong dòng thứ ba, in k số nguyên được phân tách bằng khoảng trắng - các đỉnh trên đường đi ngắn nhất theo thứ tự thăm. Đỉnh đầu tiên phải là đỉnh s, đỉnh cuối cùng phải là đỉnh t. Nếu có nhiều đường đi ngắn nhất, in bất kỳ đường đi nào."}},{"title":"Sample 1","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 4\n1 4 2\n1 2 0\n2 3 0\n3 4 0\n1 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n4\n1 2 3 4 \n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Sample 2","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 3\n1 2 4\n2 3 5\n3 4 6\n1 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e112\n4\n1 2 3 4 \n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}