Problem:
 Score : 700 points    Problem Statement You are given an integer L . Construct a directed graph that satisfies the conditions below. The graph may contain multiple edges between the same pair of vertices. It can be proved that such a graph always exists.   The number of vertices, N , is at most 20 . The vertices are given ID numbers from 1 to N .  The number of edges, M , is at most 60 . Each edge has an integer length between 0 and 10^6 (inclusive).  Every edge is directed from the vertex with the smaller ID to the vertex with the larger ID. That is, 1,2,...,N is one possible topological order of the vertices.  There are exactly L different paths from Vertex 1 to Vertex N . The lengths of these paths are all different, and they are integers between 0 and L-1 .   Here, the length of a path is the sum of the lengths of the edges contained in that path, and two paths are considered different when the sets of the edges contained in those paths are different.      Constraints  2 \leq L \leq 10^6  L is an integer.         Input Input is given from Standard Input in the following format:  L       Output In the first line, print N and M , the number of the vertices and edges in your graph.
In the i -th of the following M lines, print three integers u_i,v_i and w_i , representing the starting vertex, the ending vertex and the length of the i -th edge.
If there are multiple solutions, any of them will be accepted.        Sample Input 1 4      Sample Output 1 8 10
1 2 0
2 3 0
3 4 0
1 5 0
2 6 0
3 7 0
4 8 0
5 6 1
6 7 1
7 8 1  In the graph represented by the sample output, there are four paths from Vertex 1 to N=8 :   1 → 2 → 3 → 4 → 8 with length 0  1 → 2 → 3 → 7 → 8 with length 1  1 → 2 → 6 → 7 → 8 with length 2  1 → 5 → 6 → 7 → 8 with length 3   There are other possible solutions.       Sample Input 2 5      Sample Output 2 5 7
1 2 0
2 3 1
3 4 0
4 5 0
2 4 0
1 3 3
3 5 1

Solution (Python):
l = int(input())
n = l.bit_length()
ANS = []
for i in range(1, n):
    ANS.append((i, i + 1, 0))
    ANS.append((i, i + 1, 2**(i - 1)))
for i in reversed(range(1, n)):
    if l - 2**(i - 1) >= 2**(n - 1):
        l -= 2**(i - 1)
        ANS.append((i, n, l))
print(n, len(ANS))
for ans in ANS:
    print(*ans)

Solution (Python):
l=int(input())
for i in range(1,21):
	if 2**i>l:
		r=i-1
		break
ans=[]
for i in range(r):
	ans.append((i+1,i+2,0))
	ans.append((i+1,i+2,2**i))
now=2**r-1
for i in range(r,0,-1):
	if 2**(i-1)+now<=l-1:
		ans.append((i,r+1,now+1))
		now+=2**(i-1)
print(r+1,len(ans))
for x in ans:
	print(*x)

Solution (Python):
L = int(input())
N = len(str(bin(L)))-3
E = []

for n in range(N):
  E.append((n+1,n+2,0))
  E.append((n+1,n+2,2**(N-n-1)))
  
H = 2**N

for i,c in enumerate(str(bin((L)))[2:]):
    if c=="1" and i:
      E.append((1,i+1,H))
      H+=2**(N-i)

print(N+1,len(E))
for e in E:
  print(*e)

Solution (Python):
L = int(input())

r = 0

while 2**(r+1) <= L:
    r += 1

E = []
for i in range(1,r+1):
    E.append((i,i+1,0))
    E.append((i,i+1,2**(i-1)))

N = r+1

for i in range(N-1,0,-1):
    if L-(2**(i-1))>=2**r:
        E.append((i,N,L-2**(i-1)))
        L -= 2**(i-1)

print(N,len(E))
for e in E:
    print(e[0],e[1],e[2])

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]



def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





L = I()

N = len(bin(L))-2

ans = []
for i in range(1,N):
  if L%2:
    ans.append([i,N,L-1])
  ans.append([i,i+1,L//2])
  ans.append([i,i+1,0])
  L //= 2

print(N,len(ans))
for a,b,c in ans:
  print(a,b,c)

Solution (Python):
import sys
def I(): return int(sys.stdin.readline().rstrip())


L = I()
N = L.bit_length()
M = 2*(N-1)
ANS = [[i,i+1,0] for i in range(1,N)] + [[i,i+1,2**(N-1-i)] for i in range(1,N)]

a = 1 << (N-1)
for i in range(N-2,-1,-1):
    if (L >> i) & 1:
        ANS.append([1,N-i,a])
        M += 1
        a += 1 << i

print(N,M)
for i in range(M):
    print(*ANS[i])

Solution (Python):
L = int(input())
edges = []

p2 = 1
N = 1

""" 2べきのとき多重辺
   0     0     0     0  ...
1 === 2 === 3 === 4 === 5 ...
   1     2     4     8  ...
"""
while L >= p2 * 2:
    N += 1
    p2 *= 2
    edges.append((N - 1, N, 0))
    edges.append((N - 1, N, 2 ** (N - 2)))

rest = L - p2
tmp = p2
for i in range(N, -1, -1):
    if (rest >> i) & 1:
        edges.append((i + 1, N, tmp))
        tmp += 2 ** i

M = len(edges)

print(N, M)
for edge in edges:
    print(*edge)

Solution (Python):
L = int(input())

N = len(bin(L)[2:])
M = 2*(N-1) + bin(L)[3:].count("1")
print(N, M)

for i in range(1, N):
  print(i, i+1, 0)
  print(i, i+1, 2**(i-1))

temp = L
for i in range(1, N):
  if bin(L)[-i] == "1":
    print(i, N, temp-2**(i-1))
    temp -= 2**(i-1)

Solution (Python):
L=int(input())
N,D,p=L.bit_length(),[],print
P=1<<(N-1)
for i in range(2,N+1):
    s=N-i
    D+=[(i-1,i,0),(i-1,i,1<<s)]
    if (L>>s)&1:D+=[(1,i,P)];P+=1<<s
p(N,len(D))
for x,y,c in D:p(x,y,c)

Solution (Python):
L = int(input())
A, N, D = [(1<<i) for i in range(21)], L.bit_length(), []
for i in reversed(range(1,N)):
    D += [(i,i+1,0),(i,i+1,A[N-1-i])]
P = A[N-1]
for i in range(2,N+1):
    s = N-i
    if (L>>s)&1==1:
        D += [(1,i,P)]
        P += A[s]
print(N,len(D))
for x,y,c in D:
    print(x,y,c)

Solution (Python):
L = int(input())
ans = []
for i in range(1,19):
    ans.append((i,i+1,0))
    ans.append((i,i+1,2**(i-1)))
cur = 0
flag = True
for i in range(20)[::-1]:
    if L >> i & 1:
        if flag:
            for _ in range(2):
                ans.append((i,20,cur))
                cur += 1 << (i-1)
        else:
            ans.append((i+1,20,cur))
            cur += 1 << i
    else:
        flag = False
print(20,len(ans))
for tpl in ans:
    print(*tpl)

Solution (Python):
n=int(input())
t=n
ar=[]
while(t>0):
    ar.append(t)
    if t%2==0:
        t=t//2
    else:
        t-=1
class Graph():
    def __init__(self):
        self.vertices=set()
        self.edges=[]
    def addedge(self,a,b,w):
        self.edges.append([a,b,w])
        self.vertices.add(a)
        self.vertices.add(b)
g=Graph()
g.addedge(0,1,0)
g.addedge(0,1,1)
for i in range(3,len(ar)+1):
    if ar[-i]==ar[-i+1]+1:
        g.addedge(0,len(g.vertices)-1,ar[-i]-1)
    else:
        for j in g.edges:
            j[2]*=2
        g.addedge(len(g.vertices)-1,len(g.vertices),0)
        g.addedge(len(g.vertices)-2,len(g.vertices)-1,1)


print(len(g.vertices),len(g.edges))

for i in g.edges:
    print(i[0]+1,i[1]+1,i[2])

Solution (Python):
L = int(input())
N = L.bit_length()
res = []
for i in range(N - 1):
  res.append((i + 1, i + 2, 0))
  res.append((i + 1, i + 2, 2**i))
rem = L - 2**(N - 1) 
k = 2**(N - 1)
for i in range(rem.bit_length())[::-1]:
  if (rem >> i) & 1:
    res.append((i + 1, N, k))
    k += 2**i
print(N, len(res))
for r in res:
  print(*r)

Solution (Python):


import math

l = int(input())

r = math.floor(math.log2(l))

num_vertex = 0
num_edge = 0

num_vertex += r+1

print_list = []
for i in range(r):
    print_list.append([i+1, i+2, 0])
    print_list.append([i+1, i+2, 2**i])
    num_edge += 2


for i in reversed(range(r+1)):
    if l-2**i >= 2**r:
        print_list.append([i+1, r+1, l-2**i])
        l -= 2**i
        num_edge += 1

print(num_vertex, num_edge)
for i in print_list:
    print(*i)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt, pi
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





L = int(input())

Lstr = bin(L)[2:]

N = len(Lstr)
M = (N - 1) * 2 + (Lstr.count("1") - 1)

print(N, M)
c = 1
for i in range(1, N):
    print(i, i + 1, c)
    print(i, i + 1, 0)
    c *= 2

c = 2 ** (N - 1)
for i, v in enumerate(Lstr[::-1]):
    if i == N - 1:
        continue
    if v == "1":
        print(i + 1, N, c)
        c += 2 ** i

Solution (Python):
import sys

input = sys.stdin.readline


def main():
    L = int(input())

    Lstr = bin(L)[2:]

    N = len(Lstr)
    M = (N - 1) * 2 + (Lstr.count("1") - 1)

    print(N, M)
    c = 1
    for i in range(1, N):
        print(i, i + 1, c)
        print(i, i + 1, 0)
        c *= 2

    c = 2 ** (N - 1)
    for i, v in enumerate(Lstr[::-1]):
        if i == N - 1:
            continue
        if v == "1":
            print(i + 1, N, c)
            c += 2 ** i



if __name__ == '__main__':
    main()

Solution (Python):
L=int(input())-1
for i in range(1,21):
    if 2**i>L+1:
        N=i
        break
M=2*(N-1)
l=[]
for i in range(1,N):
    l.append((i,i+1,2**(i-1)))
    l.append((i,i+1,0))
L-=2**(N-1)-1
t=2**(N-1)
for i in range(N-1,-1,-1):
    if 2**i<=L:
        l.append((i+1,N,t))
        L-=2**i
        t+=2**i
        M+=1
print(N,M)
for i in l:
    print(*i)

Solution (Python):
L = int(input())
N = L.bit_length()
res = []
for i in range(N - 1):
    res.append((i + 1, i + 2, 0))
    res.append((i + 1, i + 2, 2**i))
rem = L - 2**(N - 1) 
k = 2**(N - 1)
for i in range(rem.bit_length())[::-1]:
    if (rem >> i) & 1:
        res.append((i + 1, N, k))
        k += 2**i
print(N, len(res))
for r in res:
    print(*r)

Solution (Python):
def main():
    L = int(input())
    n = 1
    while 2**n <= L:
        n += 1
    n -= 1
    ans = []
    for i in range(1, n+1):
        ans.append([i, i+1, 0])
        ans.append([i, i+1, 2**(i-1)])
    for i in reversed(range(1, n+1)):
        if L-2**(i-1) >= 2**n:
            ans.append([i, n+1, L-2**(i-1)])
            L -= 2**(i-1)
    print(n+1, len(ans))
    for u, v, w in ans:
        print(u, v, w)

if __name__ == "__main__":
    main()

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): 
	return list(map(int,input().split()))
def m(): 
	return map(int,input().split())
def onem(): 
	return int(input())
def s(x): 
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): 
	return " ".join(map(str,x))
def max2(x): 
	return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""

n = onem()
nn = n
N = 1
co = 0
while True:
	N *= 2
	if n < N:
		break
	co += 1
	if co > 19:
		break

data = []

ap = 1
for i in range(1,co+1):
	data.append([i,i+1,0])
	data.append([i,i+1,ap])
	ap *= 2
for i in range(co,-1,-1):
	if n - pow(2,i) >= pow(2,co):
		data.append([i+1,co+1,n-pow(2,i)])
		n -= pow(2,i)
print(co+1,len(data))
for i in range(len(data)):
	print(jo(data[i]))

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    L = int(input())
    edges = []
    vertex = 1
    flag = True
    before = -1
    for i in range(19,-1,-1):
        if (L>>i)&1:
            if flag:
                flag = False
                vertex = i + 1
                for j in range(1,vertex):
                    edges.append((j,j + 1,0))
                    edges.append((j,j + 1,1<<(j - 1)))
                before = 1<<i
            else:
                edges.append((i + 1,vertex,before))
                before += 1<<i
    print(vertex,len(edges))
    for t in edges:
        print(*t)
if __name__ == '__main__':
    main()

Solution (Python):
L = int(input())
v = 1
edges = []
n = 2
cost = 1
while n<=L:
    edges.append((v,v+1,0))
    edges.append((v,v+1,cost))
    cost *=2
    v += 1
    n *=2
goal = v
n//=2
N = n
L -=N
while L>0:
    if L>=n:
        edges.append((v,goal,N))
        L-=n
        N+=n
    n//=2
    v-=1
print(goal,len(edges))
for e in edges:
    print(*e)

Solution (Python):
l = int(input())
l -= 1
to = [[] for _ in range(14)]
for i in range(1, 13):
    to[i].append((i + 1, 0 * 3 ** (12 - i)))
    to[i].append((i + 1, 1 * 3 ** (12 - i)))
    to[i].append((i + 1, 2 * 3 ** (12 - i)))
d = []
l_upto = []
t = l
s = 0
for i in range(13):
    d.append(t % 3)
    s += (t % 3) * 3 ** i
    l_upto.append(s)
    t //= 3

for i, t in enumerate(d):
    for s in range(t + (i == 0)):
        to[0].append((13 - i, l - l_upto[i] + 3 ** i * s))
print(14, sum(map(len, to)))
for i in range(len(to)):
    for j, cost in to[i]:
        print(i + 1, j + 1, cost)

Solution (Python):
import sys

readline = sys.stdin.buffer.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    def calc(x):
        for i in range(100):
            if 2 ** (i + 1) > x:
                return i

    from collections import defaultdict

    l = int(input())
    n = calc(l) + 1
    edge = []
    for u in range(1, n):
        edge.append((u, u + 1, 0))
        edge.append((u, u + 1, 2 ** (u - 1)))

    mx = 2 ** (n - 1) - 1
    rem = (l - 1) - mx
    bit = format(rem, "b")
    bit = bit[::-1]

    cur = mx

    for u, o in enumerate(bit, 1):
        if o == "1":
            edge.append((u, n, cur + 1))
            cur += 2 ** (u - 1)

    print(n, len(edge))

    for u, v, w in edge:
        print(u, v, w)


if __name__ == '__main__':
    main()

Solution (Python):
L = int(input())
v = 1
edges = []
n = 2
cost = 1
while n <=L:
    edges.append((v,v+1,0))
    edges.append((v,v+1,cost))
    cost *=2
    v += 1
    n*=2
goal = v
n //=2
N = n
L-=N
while L>0:
    if L>=n:
        edges.append((v,goal,N))
        L-=n
        N+=n
    n //=2
    v-=1
print(goal,len(edges))
for e in edges:
    print(*e)

Solution (Python):
L = int(input())

Edges = []

n = 1
while 2**(n-1)-1 < L:
    n += 1
n -= 1

for i in range(1, n):
    Edges.append([i, i+1, 0])
    Edges.append([i, i+1, 2**(i-1)])

remain = L - 2**(n-1)
for x in range(n-1, 0, -1):
    if 2**(x-1) <= remain:
        Edges.append([x, n, L-remain])
        remain -= 2**(x-1)

print(n, len(Edges))
for u, v, w in Edges:
    print(u, v, w)

Solution (Python):
l = int(input())

b = bin(l)[2:][::-1]

l = []
for i in range(len(b)):
    if b[i] == '1':
        l.append(i)

k = l.pop()

nodes = [i for i in range(1, k + 2)]
edges = []
for i in range(len(nodes) - 1):
    edges.append([nodes[i], nodes[i+1], 2 ** (k - i - 1)])
    edges.append([nodes[i], nodes[i+1], 0])

covered = 2 ** k - 1
for x in l:
    edges.append([1, k + 1 - x, covered + 1])
    covered = edges[-1][-1] + 2 ** x - 1

print(max(nodes), len(edges))
for u, v, w in edges:
    print(u, v, w)

Solution (Python):


L = int(input())
r = 0
while pow(2, r+1) <= L:
    r += 1

N = r + 1 

edge = []
for i in range(N-1): 
    edge.append((i+1, i+2, 0))
    edge.append((i+1, i+2, pow(2, i)))

M = r * 2
remain = L - pow(2, r)

for i in range(N-1)[::-1]:
    if remain < pow(2, i):
        continue
    else:
        edge.append((i+1, N, L-remain))
        M += 1
        remain -= pow(2, i)

print(N, M)
for e in edge:
    print(' '.join(map(str, e)))

Solution (Python):
import sys
from math import ceil
def input(): return sys.stdin.readline().strip()


def main():
    L = int(input())
    """
    L=Xのときにグラフが作れたとして、L=X*2, L=X+1の２パターンを
    構成できたら辺の数をlog(L)の増大率で任意のLに対して目的のグラフを構成できる。
    L=X+1の場合はスタートとゴールの間に長さLの辺を追加するだけでよい。
    L=X*2の場合はL=Xのときの辺長をすべて２倍して、さらにゴールから長さ0, 1の二重辺をつけ足せばよい。
    """

    
    N = 2
    M = 2
    even = 0
    order = [L]
    while L != 2:
        if L % 2 == 0:
            N += 1
            M += 2
            L //= 2
            even += 1
        else:
            M += 1
            L -= 1
        order.append(L)
    print("{} {}".format(N, M))
    order.pop()
    
    
    
    print("{} {} {}".format(1, 2, 0))
    print("{} {} {}".format(1, 2, 2** even))
    edge = 2
    while order:
        L = order.pop()
        if L % 2 == 0:
            even -= 1
            print("{} {} {}".format(edge, edge + 1, 0))
            print("{} {} {}".format(edge, edge + 1, 2 ** even))
            edge += 1
        else:
            print("{} {} {}".format(1, edge, (L - 1) * 2 ** even))
            


if __name__ == "__main__":
    main()

Solution (Python):

l=int(input())
r=0
while 2**(r+1)<=l:
    r+=1
n=r+1
ans=[]
for i in range(r):
    ans.append((i+1,i+2,0))
    ans.append((i+1,i+2,2**i))

for t in range(n-1,0,-1):
    if l-2**(t-1)>=2**r:
        ans.append((t,n,l-2**(t-1)))
        l-=2**(t-1)
print(n,len(ans))
for a in ans:
    print(*a)

Solution (Python):
def main():
    l=int(input())
    n=1
    while (1<<n)<=l:
        n+=1
    ans=[]
    for i in range(n-1):
        ans.append([i,i+1,0])
        ans.append([i,i+1,1<<i])
    l-=1<<(n-1)
    val=1<<(n-1)
    for p in range(n-2,-1,-1):
        if l>=(1<<p):
            ans.append([p,n-1,val])
            val+=1<<p
            l-=1<<p
    print(n,len(ans))
    for a,b,c in ans:
        print(a+1,b+1,c)
main()

Solution (Python):
import sys
import math

input_methods=['clipboard','file','key']
using_method=1
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(IN())
mod=1000000007



def main():
	L = int(input())
	
	
	v = int(math.log2(L))
	
	num_p = v
	path_info=[]
	for i in range(v):
		path_info.append([i,i+1,0])
		path_info.append([i,i+1,2**i])
	
	
	
	
	nokori = L - (2 ** v)
	
	
	for i in range(v+1):
		m = v - i
		if 2 ** m <= nokori:
			path_info.append([m, v, L - nokori])
			nokori -= 2 ** m
	print(v+1, len(path_info))
	for l in path_info:
		f,t,w = l
		print(*[f+1, t+1, w])
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
import sys
import math

input_methods=['clipboard','file','key']
using_method=1
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(IN())
mod=1000000007



def main():
	L = int(input())
	
	
	v = int(math.log2(L))
	
	num_p = v
	path_info=[]
	for i in range(v):
		path_info.append([i,i+1,0])
		path_info.append([i,i+1,2**i])
	
	
	
	
	nokori = L - (2 ** v)
	
	
	for i in range(v+1):
		m = v - i
		if 2 ** m <= nokori:
			path_info.append([m, v, L - nokori])
			nokori -= 2 ** m
	print(v+1, len(path_info))
	for l in path_info:
		f,t,w = l
		print(*[f+1, t+1, w])
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
def main():
    L = int(input())
    r = 0
    while 2 ** (r+1) <= L:
        r += 1
    assert r < 20
    N = r + 1
    edges = list()
    for i in range(1, N):
        edges.append((i, i + 1, 0))
        edges.append((i, i + 1, 2**(i - 1)))
    for t in range(N - 1, 0, -1):
        if L - 2**(t - 1) >= 2**r:
            edges.append((t, N, L - 2**(t - 1)))
            L -= 2**(t - 1)
    print('{} {}'.format(N, len(edges)))
    for e in edges:
        print(' '.join(map(str, e)))


if __name__ == '__main__':
    main()

Solution (Python):

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

L = ir()
edges = []
length = L.bit_length()
for i in range(1, length):
    edges.append((i, i+1, 2**(i-1)))
    edges.append((i, i+1, 0))



for i in range(length-1):
    if L >> i & 1:
        L -= 2 ** i
        edges.append((i+1, length, L))

print(length, len(edges))
for x in edges:
    print(*x)

Solution (Python):
l = int(input())
n = 0
while 2**n <= l:
  n += 1
p = []
for i in range(1, n):
  p.append((i, i + 1, 0))
  p.append((i, i + 1, 2**(i-1)))
  if l // (2**(i-1)) % 2 == 1:
    p.append((i, n, l // 2**i * 2**i))
m = len(p)
print(n, m)
for i in p:
  print(*i)

Solution (Python):
L = int(input())
N = L.bit_length()

node = [i for i in range(1, N + 1)]
edge = []

for x, y in zip(node[:-1], node[1:]):
    edge.append((x, y, 0))

x = 1
while L > 1:
    if L & 1:
        L -= 1
        edge.append((x, N, L))
    else:
        L //= 2
        edge.append((x, x + 1, L))
        x += 1

print(N, len(edge))
for e in edge:
    print(*e)

Solution (Python):
from itertools import dropwhile
l=int(input())
k=[(l>>i & 1) for i in range(20)][::-1]
k=list(dropwhile(lambda x:x==0,k))

n=len(k)
path=[]
for i in range(n-1):
    path.append((i+1,i+2,0))
    path.append((i+1,i+2,2**i))

path_len=2**(n-1)
for i in range(1,n):
    if k[i]:
        x=n-1-i
        path.append((x+1,n,path_len))
        path_len+=(2**x)

m=len(path)
print(n,m)
for i in path:
    print(i[0],i[1],i[2])

Solution (Python):
l=int(input())
k=l
cnt=0
while k>1:
    k//=2
    cnt+=1
edge=[[] for _ in range(cnt)]
e=2*cnt
for i in range(cnt):
    edge[i].append((i+1,0))
    edge[i].append((i+1,2**i))
for i in reversed(range(cnt)):
    if l-2**i>=2**cnt:
        edge[i].append((cnt,l-2**i))
        l-=2**i
        e+=1
print(cnt+1,e)
for i in range(cnt):
    for j,d in edge[i]:
        print(i+1,j+1,d)

Solution (Python):
L = int(input())
k = 1
power = 4
while L >= power:
    k += 1
    power *= 2

power = 1
ans = []
for i in range(k):
    ans.append([k-i, k+1-i, 0])
    ans.append([k-i, k+1-i, power])
    power *= 2

N = k+1
l = power
rest = L - l
while rest > 0:
    power = 1
    k = 0
    while rest >= power * 2:
        power *= 2
        k += 1
    ans.append([1, N-k, l])
    l += power
    rest -= power

print(*[N, len(ans)])
for i in ans:
    print(*i)

Solution (Python):
l = int(input())

r = 1
while 2 ** r <= l:
    r += 1
r = min(19, r - 1)


n = r + 1


ts = [i for i in range(1, n)]
ts.reverse()


m = (n - 1) * 2

points = {}

for t in ts:
    a = l - 2 ** (t - 1)
    b = 2 ** r
    if a >= b:
        points[t] = a
        l -= 2 ** (t - 1)

m += len(points)
print(n, m)
for i in range(1, (n - 1) * 2 + 1):
    p = (i - 1) // 2 + 1
    if i % 2 == 0:
        print(p, p + 1, 0)
    else:
        print(p, p + 1, 2 ** (p - 1))

for k in points.keys():
    print(k, n, points[k])

Solution (Python):
l = int(input())
n = len(bin(l)) - 3
tmp = 2 ** n
print(n + 1, 2 * n + bin(l)[3:].count('1'))
for i in range(n):
    print(i+1, i+2, 0)
    print(i+1, i+2, 2 ** i)
    if l & (1<<i):
        print(i+1, n+1, tmp)
        tmp += 2 ** i

Solution (Python):
n = int(input())
ans = []
count = 1
two = 1
for i in range(20):
    if two*2 <= n:
        count += 1
        ans.append([count-1,count,0])
        ans.append([count-1,count,two])
        two *= 2
    else:
        break

for i in range(count,0,-1):
    if n - pow(2,i-1) >= two:
        
        ans.append([i,count,n-pow(2,i-1)])
        n -= pow(2,i-1)
print(count,len(ans))
for i in ans:
    print(*i)

Solution (Python):

import sys


def solve(L: int):
    sL = "{:b}".format(L)
    N = len(sL)
    M = 2 * (N - 1) + sL.count("1") - 1
    print(N, M)
    for i in range(N - 1):
        print(i + 1, i + 2, 0)
        print(i + 1, i + 2, 2 ** i)
    for i, c in enumerate(reversed(sL[1:])):
        if c == "0":
            continue
        print(i + 1, N, int(sL[:-i - 1], 2) * 2 ** (i + 1))


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    L = int(next(tokens))  
    solve(L)


if __name__ == '__main__':
    main()

Solution (Python):
L = int(input())

N = len(str(bin(L)))-2

bitL = [0] *20
splitL  = [0] * 20
sumL = [0] * 20

for i in range(19,-1,-1):
  if L % 2 == 1:
    bitL[i] = 1
  L = L // 2

for i in range(19,-1,-1):
  splitL[i] = int(bitL[i]) * 2**(19-i)

for i in range(20):

  if i == 0:
    sumL[i] = splitL[i]
  else:
    sumL[i] =splitL[i]+sumL[i-1]





edge = []
 
for i in range(N-1):
  edge.append([i+1,i+2,0])
  edge.append([i+1,i+2,2**i])


for i in range(21-N,20):
  if bitL[i] == 1:
    edge.append([20-i,N,sumL[i-1]])


print(N,len(edge))

for i in range(len(edge)):
  print(edge[i][0],edge[i][1],edge[i][2])

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product

def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

l=int(input())
r=20
while 2**r>l:
    r-=1
anslst=[]
for i in range(2*r):
    lst=[i//2+1, i//2+2, 0]
    if i%2==1:
        lst[2]=2**((i)//2)
    anslst.append(lst)

for i in range(r):
    if l-2**(r-i-1)>=2**r:
        anslst.append([r-i,r+1,l-2**(r-i-1)])
        l-=2**(r-i-1)

print(*[r+1,len(anslst)])
for i in range(len(anslst)):
    print(*anslst[i])

Solution (Python):
l=int(input())
n=len(bin(l-1))-2 
V=[]
if all([(l-1)>>i&1 for i in range(n)]):
    n+=1
    for i in range(n-1):
        V.append([i+1,i+2,0])
        V.append([i+1,i+2,2**(n-i-2)])


else:
    for i in range(n-1):
        V.append([i+1,i+2,0])
        V.append([i+1,i+2,2**(n-i-2)])

    now=2**(n-1)
    for i in range(n-2):
        if (l-1)>>(n-i-2)&1:
            V.append([1,i+2,now])
            now+=2**(n-i-2)
    if (l-1)&1:
        V.append([1,n-1,now])
    else:
        V.append([1,n,now])
print(n,len(V))
for v in V:
    print(*v)

Solution (Python):
L = int(input())

paths = []
n = 2
v = 1
while n <= L:
    paths.append((v, v+1, 0))
    paths.append((v, v+1, n//2))
    v += 1
    n *= 2
n //= 2

vlast = v
nn = n
ll = L - n

while ll > 0:
    if ll >= n:
        paths.append((v, vlast, nn))
        ll -= n
        nn += n
    n //= 2
    v -= 1

print(vlast, len(paths))
for e in paths:
    print(*e)

Solution (Python):
n=int(input())
cnt=0
while 2**cnt-1<n:
  cnt+=1
cnt-=1
graph=[]
for i in range(cnt):
  graph.append((1+i,2+i,2**i))
  graph.append((1+i,2+i,0))
existmax=2**cnt-1
for i in range(1,cnt+1)[::-1]:
    if 2**(i-1)-1+existmax+1<=n-1:
        graph.append((i,cnt+1,existmax+1))
        existmax=existmax+1+2**(i-1)-1
L=len(graph)
print(cnt+1,L)
for i in graph:
  print(*i)

Solution (Python):
L = int(input())
N = len(bin(L)[2:])
ans = []
for i in range(1, N):
    ans.append((i, i+1, 0))
    ans.append((i, i+1, 1<<(i-1)))
n = 1 << (N-1)
while n < L:
    i = 1
    while (1<<i) - 1 + n < L:
        i += 1
    ans.append((i, N, n))
    n += 1 << (i-1)
print(N, len(ans))
for a in ans:
    print(*a)

Solution (Python):
L = int(input())
def digits_count(n):
  cnt = 0
  while n != 0:
    cnt += 1
    n //= 2
  return cnt
def doubling(n, m):
  y = 1
  base = n
  while m != 0:
    if m % 2 == 1:
      y *= base
    base *= base
    m //= 2
  return y
m = digits_count(L)
A = [0 for _ in range(m)]
for i in range(m, 0, -1):
  A[i-1] = L % 2
  L //= 2
binomial = [1 for _ in range(m)]
for i in range(1, m):
  binomial[i] = binomial[i-1] * 2
vert = [[i*m+i+1, binomial[i]] for i in range(m-1)]
vert = vert[:] + [[i*m+i+1, 0] for i in range(m-1)]
S = doubling(2, m - 1)
for i in range(1, m):
  if A[i] == 1:
    vert.append([(m-i-1)*m+m-1, S])
    S += binomial[m-i-1]
print(m, len(vert))
for i in vert:
  print(i[0] // m + 1, i[0] % m + 1, i[1])