M. Moving Both Hands

problem_index: M

time_limit: 1 second

memory_limit: 256 megabytes

note:
If initially Pak Chanek's left hand is on vertex $$$1$$$ and his right hand is on vertex $$$5$$$, Pak Chanek can do the following moves:
Move his right hand to vertex $$$4$$$ in $$$1$$$ second.  Move his left hand to vertex $$$2$$$ in $$$2$$$ seconds.  Move his left hand to vertex $$$4$$$ in $$$1$$$ second.
![image](images/cf_1725_M/1.png)
In total it needs $$$1+2+1=4$$$ seconds. It can be proven that there is no other way that is faster.

solutions: ["import heapq\r\n\r\ndef main():\r\n    \r\n    n, m = readIntArr()\r\n    adjforward = [[] for _ in range(n)]\r\n    adjbackward = [[] for _ in range(n)]\r\n    for __ in range(m):\r\n        u, v, w = readIntArr()\r\n        u -= 1; v -= 1\r\n        adjforward[u].append((v, w))\r\n        adjbackward[v].append((u, w))\r\n    \r\n    inf = int(2e18)\r\n    dist = [inf] * n\r\n    dist[0] = 0\r\n    # h = [(0, 0)]\r\n    h = [0]\r\n    while h:\r\n        # d, u = heapq.heappop(h)\r\n        X = heapq.heappop(h)\r\n        d, u = divmod(X, n)\r\n        if dist[u] == d:\r\n            for v, w in adjforward[u]:\r\n                if d + w < dist[v]:\r\n                    dist[v] = d + w\r\n                    # heapq.heappush(h, (d + w, v))\r\n                    heapq.heappush(h, (d + w) * n + v)\r\n    \r\n    ans = [inf] * n\r\n    ans[0] = 0\r\n    h = []\r\n    for u in range(1, n):\r\n        if dist[u] != inf:\r\n            ans[u] = dist[u]\r\n            # h.append((dist[u], u))\r\n            h.append(dist[u] * n + u)\r\n    # h.append((0, 0))\r\n    h.append(0)\r\n    heapq.heapify(h)\r\n    while h:\r\n        # d, u = heapq.heappop(h)\r\n        X = heapq.heappop(h)\r\n        d, u = divmod(X, n)\r\n        if ans[u] == d:\r\n            for v, w in adjbackward[u]:\r\n                if d + w < ans[v]:\r\n                    ans[v] = d + w\r\n                    # heapq.heappush(h, (d + w, v))\r\n                    heapq.heappush(h, (d + w) * n + v)\r\n    ans2 = []\r\n    for u in range(1, n):\r\n        if ans[u] == inf:\r\n            ans2.append(-1)\r\n        else:\r\n            ans2.append(ans[u])\r\n    oneLineArrayPrint(ans2)\r\n    \r\n    return\r\n\r\nimport sys\r\ninput=sys.stdin.buffer.readline #FOR READING PURE INTEGER INPUTS (space separation ok)\r\n# input=lambda: sys.stdin.readline().rstrip(\"\\r\\n\") #FOR READING STRING/TEXT INPUTS.\r\n \r\ndef oneLineArrayPrint(arr):\r\n    print(' '.join([str(x) for x in arr]))\r\ndef multiLineArrayPrint(arr):\r\n    print('\\n'.join([str(x) for x in arr]))\r\ndef multiLineArrayOfArraysPrint(arr):\r\n    print('\\n'.join([' '.join([str(x) for x in y]) for y in arr]))\r\n \r\ndef readIntArr():\r\n    return [int(x) for x in input().split()]\r\n# def readFloatArr():\r\n#     return [float(x) for x in input().split()]\r\n \r\ndef makeArr(defaultValFactory,dimensionArr): # eg. makeArr(lambda:0,[n,m])\r\n    dv=defaultValFactory;da=dimensionArr\r\n    if len(da)==1:return [dv() for _ in range(da[0])]\r\n    else:return [makeArr(dv,da[1:]) for _ in range(da[0])]\r\n \r\ndef queryInteractive(a, b, c):\r\n    print('? {} {} {}'.format(a, b, c))\r\n    sys.stdout.flush()\r\n    return int(input())\r\n \r\ndef answerInteractive(x1, x2):\r\n    print('! {} {}'.format(x1, x2))\r\n    sys.stdout.flush()\r\n \r\ninf=float('inf')\r\n# MOD=10**9+7\r\n# MOD=998244353\r\n \r\nfrom math import gcd,floor,ceil\r\nimport math\r\n# from math import floor,ceil # for Python2\r\n \r\nfor _abc in range(1):\r\n    main()", "''' M. Moving Both Hands\nhttps://codeforces.com/contest/1725/problem/M\n'''\n\nimport io, os, sys\ninput = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline  # decode().strip() if str\noutput = sys.stdout.write\n\ndef debug(*args):   \n    if os.environ.get('debug') in [None, '0']: return\n    from inspect import currentframe, getframeinfo\n    from re import search\n    frame = currentframe().f_back\n    s = getframeinfo(frame).code_context[0]\n    r = search(r\"\\((.*)\\)\", s).group(1)\n    vnames = r.split(', ')\n    var_and_vals = [f'{var}={val}' for var, val in zip(vnames, args)]\n    prefix = f'{currentframe().f_back.f_lineno:02d}: '\n    print(f'{prefix}{\", \".join(var_and_vals)}')\n\nfrom types import GeneratorType\ndef bootstrap(f, stack=[]):\n    def wrappedfunc(*args, **kwargs):\n        if stack: return f(*args, **kwargs)\n        to = f(*args, **kwargs)\n        while True:\n            if type(to) is GeneratorType:\n                stack.append(to)\n                to = next(to)\n            else:\n                stack.pop()\n                if not stack: break\n                to = stack[-1].send(to)\n        return to\n    return wrappedfunc\n\nclass IntKeyDict(dict):\n    from random import randrange\n    rand = randrange(1 << 62)\n    def __setitem__(self, k, v): super().__setitem__(k^self.rand, v)\n    def __getitem__(self, k): return super().__getitem__(k^self.rand)\n    def __contains__(self, k): return super().__contains__(k^self.rand)\n    def __repr__(self): return str({k: v for k, v in self.items()})\n    def get(self, k, default=None): return super().get(k^self.rand, default)\n    def keys(self): return [k^self.rand for k in super().keys()]\n    def items(self): return [(k^self.rand, v) for k, v in super().items()]\n\nINF = float('inf')\n\n# -----------------------------------------\n\nfrom heapq import heappush, heappop, heapify\n\ndef main():\n    N, M = list(map(int, input().split()))\n\n    adj = [[] for _ in range(N)]\n    adj_rev = [[] for _ in range(N)]\n    for _ in range(M):\n        u, v, w = list(map(int, input().split()))\n        adj[u - 1].append((v - 1, w))\n        adj_rev[v - 1].append((u - 1, w))\n\n    dist = [INF] * N \n    dist[0] = 0\n\n    # min dist from 0\n    h = [(0, 0)]\n    while h:\n        d, u = heappop(h)\n        if dist[u] < d: continue\n        for v, w in adj[u]: \n            if dist[v] <= d + w: continue\n            dist[v] = d + w \n            heappush(h, (d + w, v))\n    \n    # branch\n    h = [(d, u) for u, d in enumerate(dist) if d < INF]\n    heapify(h)\n \n    while h:\n        d, u = heappop(h)\n        if dist[u] < d: continue\n        for v, w in adj_rev[u]:\n            if dist[v] <= w + d: continue\n            dist[v] = w + d\n            heappush(h, (d + w, v))\n    \n    for u in range(N):\n        if dist[u] is INF: dist[u] = -1\n \n    print(*dist[1:])\n\n\nif __name__ == '__main__':\n    main()", "import io, os, sys\r\ninput = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline  # decode().strip() if str\r\noutput = sys.stdout.write\r\n\r\nINF = 1<<60\r\nfrom heapq import heappush, heappop, heapify\r\n\r\ndef main():\r\n    N, M = list(map(int, input().split()))\r\n\r\n    adj = [[] for _ in range(N)]\r\n    adj_rev = [[] for _ in range(N)]\r\n    for _ in range(M):\r\n        u, v, w = list(map(int, input().split()))\r\n        adj[u - 1].append((v - 1, w))\r\n        adj_rev[v - 1].append((u - 1, w))\r\n\r\n    # min dist from 0\r\n    dist = [INF] * N \r\n    h = [(0, 0)]\r\n    dist[0] = 0\r\n    while h:\r\n        d, u = heappop(h)\r\n        if dist[u] < d: continue\r\n        \r\n        for v, w in adj[u]: \r\n            if w + d < dist[v]:\r\n                dist[v] = w + d\r\n                heappush(h, (d + w, v))\r\n    \r\n    # branch\r\n    h = [(d, u) for u, d in enumerate(dist) if d < INF]\r\n    heapify(h)\r\n \r\n    while h:\r\n        d, u = heappop(h)\r\n        if dist[u] < d : continue\r\n        for v, w in adj_rev[u]:\r\n            if w + d < dist[v] :\r\n                dist[v] = w + d\r\n                heappush(h, (d + w, v))\r\n    \r\n    for u in range(N):\r\n        if dist[u] is INF: dist[u] = -1\r\n \r\n    print(*dist[1:])\r\n\r\nif __name__ == '__main__':\r\n    main()", "import io, os, sys\r\ninput = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline  # decode().strip() if str\r\noutput = sys.stdout.write\r\n\r\nINF = float('inf')\r\nfrom heapq import heappush, heappop, heapify\r\n\r\ndef main():\r\n    N, M = list(map(int, input().split()))\r\n\r\n    adj = [[] for _ in range(N)]\r\n    adj_rev = [[] for _ in range(N)]\r\n    for _ in range(M):\r\n        u, v, w = list(map(int, input().split()))\r\n        adj[u - 1].append((v - 1, w))\r\n        adj_rev[v - 1].append((u - 1, w))\r\n\r\n    # min dist from 0\r\n    dist = [INF] * N \r\n    h = [(0, 0)]\r\n    dist[0] = 0\r\n    while h:\r\n        d, u = heappop(h)\r\n        if dist[u] < d: continue\r\n        \r\n        for v, w in adj[u]: \r\n            if w + d < dist[v]:\r\n                dist[v] = w + d\r\n                heappush(h, (d + w, v))\r\n    \r\n    # branch\r\n    h = [(d, u) for u, d in enumerate(dist) if d < INF]\r\n    heapify(h)\r\n \r\n    while h:\r\n        d, u = heappop(h)\r\n        if dist[u] < d : continue\r\n        for v, w in adj_rev[u]:\r\n            if w + d < dist[v] :\r\n                dist[v] = w + d\r\n                heappush(h, (d + w, v))\r\n    \r\n    for u in range(N):\r\n        if dist[u] is INF: dist[u] = -1\r\n \r\n    print(*dist[1:])\r\n\r\nif __name__ == '__main__':\r\n    main()", "import os, sys\r\nfrom io import BytesIO, IOBase\r\nfrom array import array\r\nimport heapq\r\n\r\n\r\nclass FastIO(IOBase):\r\n    newlines = 0\r\n\r\n    def __init__(self, file):\r\n        self._fd = file.fileno()\r\n        self.buffer = BytesIO()\r\n        self.writable = \"x\" in file.mode or \"r\" not in file.mode\r\n        self.write = self.buffer.write if self.writable else None\r\n\r\n    def read(self):\r\n        while True:\r\n            b = os.read(self._fd, max(os.fstat(self._fd).st_size, 8192))\r\n            if not b:\r\n                break\r\n            ptr = self.buffer.tell()\r\n            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)\r\n        self.newlines = 0\r\n        return self.buffer.read()\r\n\r\n    def readline(self):\r\n        while self.newlines == 0:\r\n            b = os.read(self._fd, max(os.fstat(self._fd).st_size, 8192))\r\n            self.newlines = b.count(b\"\\n\") + (not b)\r\n            ptr = self.buffer.tell()\r\n            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)\r\n        self.newlines -= 1\r\n        return self.buffer.readline()\r\n\r\n    def flush(self):\r\n        if self.writable:\r\n            os.write(self._fd, self.buffer.getvalue())\r\n            self.buffer.truncate(0), self.buffer.seek(0)\r\n\r\n\r\nclass IOWrapper(IOBase):\r\n    def __init__(self, file):\r\n        self.buffer = FastIO(file)\r\n        self.flush = self.buffer.flush\r\n        self.writable = self.buffer.writable\r\n        self.write = lambda s: self.buffer.write(s.encode(\"ascii\"))\r\n        self.read = lambda: self.buffer.read().decode(\"ascii\")\r\n        self.readline = lambda: self.buffer.readline().decode(\"ascii\")\r\n\r\n\r\nsys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)\r\n\r\ninput = lambda: sys.stdin.readline().strip()\r\nints = lambda: list(map(int, input().split()))\r\nInt = lambda: int(input())\r\n\r\n\r\ndef queryInteractive(a, b, c):\r\n    print('? {} {} {}'.format(a, b, c))\r\n    sys.stdout.flush()\r\n    return int(input())\r\n\r\n\r\ndef answerInteractive(x1, x2):\r\n    print('! {} {}'.format(x1, x2))\r\n    sys.stdout.flush()\r\n\r\n\r\ninf = float('inf')\r\n\r\n\r\nn, m = ints()\r\n\r\ng = [[] for _ in range(2 * n)]\r\nfor i in range(n):\r\n    g[i].append((i + n, 0))\r\nfor _ in range(m):\r\n    u, v, w = ints()\r\n    u -= 1\r\n    v -= 1\r\n    g[u].append((v, w))\r\n    g[v + n].append((u + n, w))\r\n\r\ndist = [inf] * 2 * n\r\ndist[0] = 0\r\nq = [(dist[0], 0)]\r\n\r\nwhile q:\r\n    d, x = heapq.heappop(q)\r\n    if dist[x] < d:\r\n        continue\r\n    for y, cost in g[x]:\r\n        if dist[x] + cost < dist[y]:\r\n            dist[y] = dist[x] + cost\r\n            heapq.heappush(q, (dist[y], y))\r\n\r\nans = [dist[i] if dist[i] != inf else -1 for i in range(n + 1, 2 * n)]\r\nprint(*ans)"]

source: codeforces

raw_problem:
M. Moving Both Hands

time limit per test
1 second

memory limit per test
256 megabytes

input
standard input

output
standard output

Pak Chanek is playing one of his favourite board games. In the game, there is a directed graph with $$$N$$$ vertices and $$$M$$$ edges. In the graph, edge $$$i$$$ connects two different vertices $$$U_i$$$ and $$$V_i$$$ with a length of $$$W_i$$$. By using the $$$i$$$-th edge, something can move from $$$U_i$$$ to $$$V_i$$$, but not from $$$V_i$$$ to $$$U_i$$$.

To play this game, initially Pak Chanek must place both of his hands onto two different vertices. In one move, he can move one of his hands to another vertex using an edge. To move a hand from vertex $$$U_i$$$ to vertex $$$V_i$$$, Pak Chanek needs a time of $$$W_i$$$ seconds. Note that Pak Chanek can only move one hand at a time. This game ends when both of Pak Chanek's hands are on the same vertex.

Pak Chanek has several questions. For each $$$p$$$ satisfying $$$2 \leq p \leq N$$$, you need to find the minimum time in seconds needed for Pak Chanek to end the game if initially Pak Chanek's left hand and right hand are placed on vertex $$$1$$$ and vertex $$$p$$$, or report if it is impossible.

Input

The first line contains two integers $$$N$$$ and $$$M$$$ ($$$2 \leq N \leq 10^5$$$, $$$0 \leq M \leq 2 \cdot 10^5$$$) — the number of vertices and edges in the graph.

The $$$i$$$-th of the next $$$M$$$ lines contains three integers $$$U_i$$$, $$$V_i$$$, and $$$W_i$$$ ($$$1 \le U_i, V_i \le N$$$, $$$U_i \neq V_i$$$, $$$1 \le W_i \le 10^9$$$) — a directed edge that connects two different vertices $$$U_i$$$ and $$$V_i$$$ with a length of $$$W_i$$$. There is no pair of different edges $$$i$$$ and $$$j$$$ such that $$$U_i = U_j$$$ and $$$V_i = V_j$$$.

Output

Output a line containing $$$N-1$$$ integers. The $$$j$$$-th integer represents the minimum time in seconds needed by Pak Chanek to end the game if initially Pak Chanek's left hand and right hand are placed on vertex $$$1$$$ and vertex $$$j+1$$$, or $$$-1$$$ if it is impossible.

Example

Input

5 7
1 2 2
2 4 1
4 1 4
2 5 3
5 4 1
5 2 4
2 1 1

Output

1 -1 3 4

Note

If initially Pak Chanek's left hand is on vertex $$$1$$$ and his right hand is on vertex $$$5$$$, Pak Chanek can do the following moves:

 Move his right hand to vertex $$$4$$$ in $$$1$$$ second.

 Move his left hand to vertex $$$2$$$ in $$$2$$$ seconds.

 Move his left hand to vertex $$$4$$$ in $$$1$$$ second.

In total it needs $$$1+2+1=4$$$ seconds. It can be proven that there is no other way that is faster.

question:
Pak Chanek is playing one of his favourite board games. In the game, there is a directed graph with $$$N$$$ vertices and $$$M$$$ edges. In the graph, edge $$$i$$$ connects two different vertices $$$U_i$$$ and $$$V_i$$$ with a length of $$$W_i$$$. By using the $$$i$$$-th edge, something can move from $$$U_i$$$ to $$$V_i$$$, but not from $$$V_i$$$ to $$$U_i$$$.
To play this game, initially Pak Chanek must place both of his hands onto two different vertices. In one move, he can move one of his hands to another vertex using an edge. To move a hand from vertex $$$U_i$$$ to vertex $$$V_i$$$, Pak Chanek needs a time of $$$W_i$$$ seconds. Note that Pak Chanek can only move one hand at a time. This game ends when both of Pak Chanek's hands are on the same vertex.
Pak Chanek has several questions. For each $$$p$$$ satisfying $$$2 \leq p \leq N$$$, you need to find the minimum time in seconds needed for Pak Chanek to end the game if initially Pak Chanek's left hand and right hand are placed on vertex $$$1$$$ and vertex $$$p$$$, or report if it is impossible.

Input
The first line contains two integers $$$N$$$ and $$$M$$$ ($$$2 \leq N \leq 10^5$$$, $$$0 \leq M \leq 2 \cdot 10^5$$$) — the number of vertices and edges in the graph.
The $$$i$$$-th of the next $$$M$$$ lines contains three integers $$$U_i$$$, $$$V_i$$$, and $$$W_i$$$ ($$$1 \le U_i, V_i \le N$$$, $$$U_i \neq V_i$$$, $$$1 \le W_i \le 10^9$$$) — a directed edge that connects two different vertices $$$U_i$$$ and $$$V_i$$$ with a length of $$$W_i$$$. There is no pair of different edges $$$i$$$ and $$$j$$$ such that $$$U_i = U_j$$$ and $$$V_i = V_j$$$.

Output
Output a line containing $$$N-1$$$ integers. The $$$j$$$-th integer represents the minimum time in seconds needed by Pak Chanek to end the game if initially Pak Chanek's left hand and right hand are placed on vertex $$$1$$$ and vertex $$$j+1$$$, or $$$-1$$$ if it is impossible.

Example
Input
5 7
1 2 2
2 4 1
4 1 4
2 5 3
5 4 1
5 2 4
2 1 1

Output
1 -1 3 4

Note
If initially Pak Chanek's left hand is on vertex $$$1$$$ and his right hand is on vertex $$$5$$$, Pak Chanek can do the following moves:
 -  Move his right hand to vertex $$$4$$$ in $$$1$$$ second. -  Move his left hand to vertex $$$2$$$ in $$$2$$$ seconds. -  Move his left hand to vertex $$$4$$$ in $$$1$$$ second. ![image](1.png)
In total it needs $$$1+2+1=4$$$ seconds. It can be proven that there is no other way that is faster.

data_split: test


Jaggie Spheres

source: ACM-ICPC Japan Alumni Group Summer Camp 2007 Day 3

raw_problem:
Problem B: Jaggie Spheres

Let J(n) be a three-dimensional body that

 is a union of unit cubes whose all vertices lie on integer coordinates,

 contains all points that are closer than the distance of √n to the origin, and

 is the smallest of all such bodies.

The figure below shows how J(1), J(2), and J(3) look.

Figure 1: Jaggie Spheres for n = 1, 2, 3

Your task is to calculate how many faces J(n) have. Here, we define two square belong to the same face
if they are parallel and share an edge, but don’t if they share just a vertex.

Input

The input consists of multiple data sets, each of which comes with a single line containing an integer n
(1 ≤ n ≤ 1000000). The end of input is indicated by n = 0.

Output

For each data set, print the number of faces J(n) have.

Sample Input

1
2
3
4
0

Output for the Sample Input

6
30
30
6

source: aizu

question:
Problem B: Jaggie Spheres

Let J(n) be a three-dimensional body that

-  is a union of unit cubes whose all vertices lie on integer coordinates,
-  contains all points that are closer than the distance of √n to the origin, and
-  is the smallest of all such bodies.

The figure below shows how J(1), J(2), and J(3) look.

![image](1.png)
Figure 1: Jaggie Spheres for n = 1, 2, 3

Your task is to calculate how many faces J(n) have. Here, we define two square belong to the same face
if they are parallel and share an edge, but don’t if they share just a vertex.

Input

The input consists of multiple data sets, each of which comes with a single line containing an integer n
(1 ≤ n ≤ 1000000). The end of input is indicated by n = 0.

Output

For each data set, print the number of faces J(n) have.

Sample Input

1
2
3
4
0

Output for the Sample Input

6
30
30
6

data_split: test