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):
import math
L=int(input())-1
  
if L==0:
  print(2,2)
  print(1,2,0)
  exit()
elif L==1:
  print(2,2)
  print(1,2,0)
  print(1,2,1)
  exit()

L2=int(math.log2(L))
LLL=2**(L2-1)
lll=LLL*2-1

branch_list=[]
for x in range(1,L2+1):
  branch_list.append([x,x+1,0])
  branch_list.append([x,x+1,LLL])
  LLL//=2


lll+=1
while True:
  ls=L-lll
  if ls<=0:
    branch_list.append([1,L2+1,lll])
    break
  else:
    ls2=int(math.log2(ls))
    branch_list.append([1,L2+1-ls2,lll])
    lll+=2**ls2

print (L2+1,len(branch_list))
for x,y,z in branch_list:
  print (x,y,z)

Solution (Python):
l=int(input())
s=len(bin(l))-3
a=1
b=0
d=[[0,0,0]for i in range(60)]
for i in range(s):
    d[b]=[a,a+1,2**(a-1)]
    d[b+1]=[a,a+1,0]
    b+=2
    a+=1
for i in range(a-1,0,-1):
    if l-2**(i-1)>=2**s:
        d[b]=[i,a,l-2**(i-1)]
        l-=2**(i-1)
        b+=1
d=[a for a in d if a!=[0,0,0]]
print(a,len(d))
for i in d:
    print(i[0],i[1],i[2])

Solution (Python):
class Solver(object):
    def __init__(self):
        self.l = int(input())
        self.n_nodes = None
        self.edges = []

    def solve(self):
        
        
        n_digits = Solver.count_bin_digits(self.l) - 1
        self.initialize_graph(n_digits)
        next_num = 2**n_digits
        leftover = self.l - 2**n_digits
        while leftover > 0:
            n_digits = Solver.count_bin_digits(leftover) - 1
            self.edges.append((1, self.n_nodes - n_digits, next_num))
            leftover -= 2**n_digits
            next_num += 2**n_digits

        print(self.n_nodes, len(self.edges))
        for e in self.edges:
            print(e[0], e[1], e[2])

    def initialize_graph(self, n_digits):
        """
        Initialize a power of two graph which can represent
        2**n_digits value. This graph would have
        Total nodes: n_digits + 1
        Total edges: 2 * n_digits
        """
        self.n_nodes = n_digits + 1
        for i in range(n_digits):  
            node = self.n_nodes - i  
            self.edges.append((node-1, node, 0))
            self.edges.append((node-1, node, 2**i))

    @staticmethod
    def count_bin_digits(n):
        return len(bin(n)) - 2

if __name__ == "__main__":
    s = Solver()
    s.solve()

Solution (Python):
from sys import stdin
L = int(stdin.readline())

tmp = 1
i = 0
while tmp <= L:
    tmp *= 2
    i += 1
N = i

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

while i != 0:
    if L-2**(i-1) >= 2**(N-1):
        path.append([i, N, L-2**(i-1)])
        L -= 2**(i-1)
        M += 1
        continue
    i -= 1

print('%d %d' % (N, M))
for elem in path:
    print(' '.join(map(str, elem)))

Solution (Python):
n = input()
node = 0
tmp = n
while tmp:
	node += 1
	tmp >>= 1
edges = []
for i in range(node - 1):
	edges.append([i+1, i+2, 0])
	edges.append([i+1, i+2, 1<<i])
for i in range(node-2, -1, -1):
	if (1<<i)&n:
		edges.append([i+1, node, (n>>(i+1))<<(i+1)])
print node, len(edges)
for i in edges:
	print i[0], i[1], i[2]

Solution (Python):
def construct(L):
    if L <= 5: return [(1,2,x) for x in range(1,L+1)], 2
    h = L//2
    e, n = construct(h)
    e.append((n, n+1, 0))
    e.append((n, n+1, h))
    if h*2 != L: e.append((1, n+1, L))
    return e, n+1

L = int(input())-1
e, n = construct(L)
e.append((1, n, 0))
print(n, len(e))
for T in e: print(*T)

Solution (Python):
def ge(k,array,ind):
    return array[ind]>=k

def lower_bound(k, array, func=ge):
    """
    k 以上を満たす最小のインデックスを返す
    もしなかったら要素数を返す
    """
    lb=-1
    ub=len(array)
    while ub-lb>1:
        mid = (lb+ub)//2
        if func(k,array,mid):
            ub=mid
        else:
            lb=mid
    return ub

def lt(k,array,ind):
    return array[ind]<k

def upper_bound(k, array, func=lt):
    """
    k 未満を満たす最大のインデックスを返す
    もしなかったら-1を返す
    """
    lb=-1
    ub=len(array)
    while ub-lb>1:
        mid = (lb+ub)//2
        if func(k,array,mid):
            lb=mid
        else:
            ub=mid
    return ub-1
def main():
    l = int(input())
    ans = []
    array = [i for i in range(60)]
    ind = upper_bound(l, array, lambda k,array,mid:2**mid<=k)
    r = array[ind]
    n = r+1
    for i in range(1,n):
        ans.append((i,i+1,0))
        ans.append((i,i+1,2**(i-1)))
    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 f,t,c in ans:
        print(f,t,c)

if __name__ == '__main__':
    main()

Solution (Python):
L=int(input())
keta=0
while(2**keta -1<L):
    keta+=1


edge=[]
tmp=1
for i in range(0,keta-1):
    edge.append("{} {} 0".format(keta-1-i,keta-i))
    edge.append("{} {} {}".format(keta-1-i,keta-i,tmp))
    tmp*=2
    if(L & 1<<(keta-2-i)):
        edge.append("{} {} {}".format(keta-1-i,keta,tmp))
        tmp+=1

if(L==1):
    edge=["1 2 0"]

print("{} {}".format(keta,len(edge)))
for e in edge:
    print(e)

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

bL = bin(L)[2:]

l = len(bL)

edges = []

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

w = 2**(l-1)
    
for idx, a in enumerate(bL):
    if idx == 0:
        continue
    if a == '0':
        continue
    n = l - idx
    edges.append([n, l, w])
    w += 2**(n-1)

print(l, len(edges))

for e in edges:
    print(e[0], e[1], e[2])

Solution (Python):
l = int(input())
ed = []
n = 20
for i in range(2, n):
    ed.append([i, i + 1, 0])
    ed.append([i, i + 1, 2 ** (n - 1 - i)])
now = 0
if l >= 2 ** 19:
    now += 1 << 19
    i = 1
    ed.append([i, i + 1, 0])
    ed.append([i, i + 1, 2 ** (n - 1 - i)])
for i in range(18, -1, -1):
    if (l >> i) & 1 == 1:
        ed.append([1, n - i, now])
        now += 1 << i
print(n, len(ed))
for i in ed:
    print(i[0], i[1], i[2])

Solution (Python):
L = int(input())
def divideBin(n):
    d = 1
    ans=[]
    while n > 0:
        r,q=divmod(n,2)
        ans.append(q*d)
        d *= 2
        n = r
    return(ans)
divided = divideBin(L)
N = len(divided)
M = 2*(N-1) + len([x for x in divided if x!=0]) - 1
print(N,M)
for i in range(1,N):
    print(i,i+1,0)
    print(i,i+1,pow(2,i-1))
node = N-1
value = divided[N-1]
while node > 0:
    if divided[node-1] != 0:
        print(node,N,value)
        value += divided[node-1]
    node -= 1

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

bL = bin(L)[2:]
N = len(bL)
M = 0
result = []
for i in range(N-1):
    result.append((N-i-1, N-i, pow(2, i)))
    result.append((N-i-1, N-i, 0))
    M += 2

max_n = pow(2, N-1) - 1
for i, j in enumerate(bL[1:][::-1]):
    if j == "1":
        result.append((1, N-i, max_n + 1))
        max_n += pow(2, i)
        M += 1

print(N, M)
for item in result:
    print(item[0], item[1], item[2])

Solution (Python):
L = int( input())
r = 0
A = []
l = L
ANS = []
while l != 0:
    l, r = divmod(l, 2)
    A.insert(0,r)
N = len(A)
for i in range(N-1):
    ANS.append("{} {} {}".format(i+1, i+2, 0))
    ANS.append("{} {} {}".format(i+1, i+2, 2**i))
del A[0]
y = 2**(N-1)
M = 2*(N-1)

for i in range(N-1):


    if A[i] == 1:
        ANS.append("{} {} {}".format(N-i-1, N, y))
        M += 1
        y += A[i]*(2**(N-i-2))

print("{} {}".format(N, M))
for a in ANS:
    print(a)

Solution (Python):
def floor_pow2(n):
    res = 0
    while 2**res <= n:
        res += 1
    return res-1
 
n = int(input())
n -= 1
 
if n <= 3:
    N = 2
    M = n+1
    print(N, M)
    for i in range(M):
        print(1, 2, i)
    exit(0)
 

N = floor_pow2(n) + 1
M = 0
 

G = [[] for i in range(N)]
 
for i in range(1,N,1):
    G[i].append([i-1, 2**(i-1)])
    G[i].append([i-1, 0])
    M += 2
 
bias = 2 ** (N - 1)
u = n - bias
 
while True:
    if u <= 1:
        G[-1].append([u, bias])
        M += 1
        break
 
    tu = floor_pow2(u)
    G[-1].append([tu, bias])
    bias += 2 ** tu
    u -= 2 ** tu
    M += 1
 
print(N, M)
for ix, es in enumerate(G):
    for e in es:
        print(N-ix, N-e[0], e[1])

Solution (Python):
def floor_pow2(n):
    res = 0
    while 2**res <= n:
        res += 1
    return res-1

n = int(input())
n -= 1

if n <= 3:
    N = 2
    M = n+1
    print(N, M)
    for i in range(M):
        print(1, 2, i)
    exit(0)


N = floor_pow2(n) + 1
M = 0


G = [[] for i in range(N)]

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

bias = 2 ** (N - 1)
u = n - bias

while True:
    if u <= 1:
        G[-1].append([u, bias])
        M += 1
        break

    tu = floor_pow2(u)
    G[-1].append([tu, bias])
    bias += 2 ** tu
    u -= 2 ** tu
    M += 1

print(N, M)
for ix, es in enumerate(G):
    for e in es:
        print(N-ix, N-e[0], e[1])

Solution (Python):
L=int(input());S=bin(L);N=len(S)-2;print(N,N+N+S.count("1")-3)
for i in range(1,N):
 x=i-1;print(i,-~i,1<<x,i,-~i,0)
 if int(S[-i]):L^=1<<x;print(i,N,L)

Solution (Python):
L=int(input());S=bin(L);N=len(S)-2;print(N,N+N+S.count("1")-3)
for i in range(N-1):
 print(i+1,i+2,1<<i,i+1,i+2,0)
 if int(S[-i-1]):L^=1<<i;print(i+1,N,L)

Solution (Python):
L=int(input());S=bin(L);N=len(S)-2;print(N,N+N+S.count("1")-3)
for i in range(1,N):
 print(i,-~i,1<<~-i,i,-~i,0)
 if int(S[-i]):L^=1<<~-i;print(i,N,L)

Solution (Python):
p=lambda x,y,z:print(x,y,z);L=int(input());S=bin(L);N=len(S)-2;p(N,N+N+S.count("1")-3,"")
for i in range(1,N):
 p(i,-~i,0);p(i,-~i,1<<~-i)
 if int(S[-i]):L^=1<<~-i;p(i,N,L)

Solution (Python):
p=lambda x,y,z:print(x,y,z);L=int(input());S=bin(L);N=len(S)-2;print(N,N+N+S.count("1")-3)
for i in range(1,N):
 p(i,-~i,0);p(i,-~i,1<<~-i)
 if int(S[-i]):L^=1<<~-i;p(i,N,L)

Solution (Python):

import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

l = ni()
n = len(bin(l)[2:])

graph = []


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

res = 2**(n-1)
for j in range(n-1, 0, -1):
    if l - res >= 2**(j-1):
        graph.append((j, n, res))
        res += 2**(j-1)
        

print(n, len(graph))
for edge in graph:
    print(*edge)

Solution (Python):

import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

l = ni()
n = len(bin(l)[2:])

graph = []


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

res = l
for j in range(n-1, 0, -1):
    if res - 2**(j-1) >= 2**(n-1):
        graph.append((j, n, res-2**(j-1)))
        res -= 2**(j-1)
        

print(n, len(graph))
for edge in graph:
    print(*edge)

Solution (Python):
L=int(input())
s=bin(L)[2:]
l=len(s)-1
ans=[]
for i in range(l):
    ans.append([i+1,i+2,2**(l-i-1)])
    ans.append([i+1,i+2,0])
u=2**(l)
for k in range(1,l+1):
    if s[k]!='0':
        ans.append([1,k+1,u])
        u+=2**(l-k) 
        
print(l+1,len(ans))
for a,b,c in ans:
    print(a,b,c)

Solution (Python):
L=int(input());S=bin(L);N=len(S)-2;print(N,N+N+S.count("1")-3)
for i in range(1,N):
 for j in[0,1]:print(i,-~i,j<<~-i)
 if int(S[-i]):L^=1<<~-i;print(i,N,L)

Solution (Python):
import itertools as I;L=int(input());S=bin(L);N=len(S)-2;print(N,N+N+S.count("1")-3)
for i,j in I.product(range(1,N),[0,1]):
 print(i,-~i,j*2**~-i)
 if int(S[-i])&j:L^=2**~-i;print(i,N,L)

Solution (Python):
from itertools import *;L=int(input());S=bin(L);N=len(S)-2;print(N,N+N+S.count("1")-3)
for i,j in product(range(1,N),[0,1]):
 print(i,-~i,j*2**~-i)
 if int(S[-i])&j:L^=2**~-i;print(i,N,L)

Solution (Python):
L=int(input());S=bin(L);N=len(S)-2;print(N,N+N+S.count("1")-3)
for i in range(1,N):
 print(i,-~i,0);print(i,-~i,2**~-i)
 if int(S[-i]):L^=2**~-i;print(i,N,L)

Solution (Python):
L=int(input());S=bin(L);N=len(S)-2;print(N,2*N+S.count("1")-3)
for i in range(1,N):
 for j in[0,1]:print(i,i+1,j*2**~-i)
 if int(S[-i]):L^=2**~-i;print(i,N,L)

Solution (Python):
L=int(input());S=bin(L);N=len(S)-2;print(N,2*N+S.count("1")-3)
for i in range(1,N):
 for j in[0,1]:print(i,i+1,j*2**i//2)
 if int(S[-i]):L^=2**i//2;print(i,N,L)

Solution (Python):
L=int(input());S=bin(L);N=len(S)-2;print(N,2*N+S.count("1")-3)
for i in range(1,N):
 for j in[0,1]:print(i,i+1,j*2**(i-1))
 if int(S[-i]):L^=2**(i-1);print(i,N,L)

Solution (Python):
L=int(input());S=bin(L);N=len(S)-2;print(N,2*N+S.count("1")-3)
for i in range(N-1):
 for j in[0,1]:print(i+1,i+2,j*2**i)
 if S[N+1-i]=="1":L^=2**i;print(i+1,N,L)

Solution (Python):
L=int(input());S=bin(L);N=len(S)-2;print(N,2*N+S.count("1")-3)
for i in range(N-1):
 print(i+1,i+2,0,"\n"+str(i+1),i+2,2**i)
 if S[N+1-i]=="1":L-=2**i;print(i+1,N,L)

Solution (Python):
L=int(input());S=bin(L);N=len(S)-2;print(N,2*N+S.count("1")-3)
for i in range(N-1):
 print(i+1,i+2,0);print(i+1,i+2,2**i)
 if S[N+1-i]=="1":L-=2**i;print(i+1,N,L)

Solution (Python):
L=int(input());S=bin(L)[2:];N=len(S);print(N,2*N+S.count("1")-3)
for i in range(N-1):
 print(i+1,i+2,0);print(i+1,i+2,2**i)
 if S[N-1-i]=="1":L-=2**i;print(i+1,N,L)

Solution (Python):
L=int(input());S=str(bin(L))[2:][::-1];N=len(S);print(N,2*N+S.count("1")-3)
for i in range(N-1):
 print(i+1,i+2,0);print(i+1,i+2,2**i)
 if S[i]=="1":L-=2**i;print(i+1,N,L)

Solution (Python):
L=int(input())
S=str(bin(L))[2:][::-1]
N=len(S)
print(N,(N-1)*2+S.count("1")-1)
for i in range(N-1):
    print(i+1,i+2,0)
    print(i+1,i+2,2**i)
for i in range(N-1):
    if S[i]=="1":
        L-=2**i
        print(i+1,N,L)

Solution (Python):
L=int(input())
S=str(bin(L))[2:][::-1]
N=len(S)
A=[]
for i in range(N-1):
    A.append((i+1,i+2,0))
    A.append((i+1,i+2,2**i))
for i in range(N-1):
    if S[i]=="1":
        L-=2**i
        A.append((i+1,N,L))
print(N,len(A))
for p in A:
    print(p[0],p[1],p[2])

Solution (Python):
L=int(input())
S=str(bin(L))[2:][::-1]
N=len(S)
A=[]
for i in range(1,N):
    A.append((i,i+1,0))
    A.append((i,i+1,2**(i-1)))

for i in range(N-1):
    if S[i]=="1":
        L-=2**i
        A.append((i+1,N,L))
print(N,len(A))
for p in A:
    print(p[0],p[1],p[2])

Solution (Python):
L = int(input())
dig = 1
for i in range(1,21):
    if (1 << i) > L:
        dig = i
        break

edge = []
for i in range(dig-1):
    if (L >> i) & 1:
        edge.append((i+1,dig,L-(1<<i)))
        L = L-(1<<i)

for i in range(dig-1):
    edge.append((i+1,i+2,0))
    edge.append((i+1,i+2,1<<i))

print(str(dig) + " " + str(len(edge)))
s = "{0} {1} {2}"
for v,v2,w in edge:
    print(s.format(v,v2,w))

Solution (Python):
k=int(input())
g = []
i = 0
while k >3:
  if k%2 == 1:
    g.append([1,20-i,(k-1)*2**i])
    k = k//2
    g.append([20-i-1,20-i,0])
    g.append([20-i-1,20-i,1*2**i])
    i+=1
  else:
    k = k//2
    g.append([20-i-1,20-i,0])
    g.append([20-i-1,20-i,1*2**i])
    i+=1
if k==3:
  g.append([1,20-i,(k-1)*2**i])
  k = k//2
  g.append([20-i-1,20-i,0])
  g.append([20-i-1,20-i,1*2**i])
  if 20-i-1 != 1:
    g.append([1,20-i-1,0])
elif k == 2:
  g.append([20-i-1,20-i,0])
  g.append([20-i-1,20-i,1*2**i])
  if 20-i-1 != 1:
    g.append([1,20-i-1,0])
print(20,len(g))
for x,y,z in g:
  print(x,y,z)

Solution (Python):
l = int(input())
edge = []
for i in range(1, 19):
    edge.append((i, i + 1, 1 << (i - 1)))
    edge.append((i, i + 1, 0))
sm = 0
for i in range(19, 0, -1):
    v = 1 << (i - 1)
    while l >= v:
        edge.append((i, 20, sm))
        sm += v
        l -= v
print(20, len(edge))
for x, y, z in edge:
    print(x, y, z)

Solution (Python):
L = int(input())
n = 2
es = [(1,2,0), (1,2,1)]
limit = 2

def double():
    global es,limit,n
    _es = []
    for a,b,w in es:
        _es.append((a,b,2*w))
    _es.append((n,n+1,0))
    _es.append((n,n+1,1))
    n += 1
    es = _es
    limit *= 2

def add_bypass():
    global es,limit
    es.append((1,n,limit))
    limit += 1

for c in str(bin(L))[3:]: 
    if c == '1':
        add_bypass()
    if limit == L:
        break
    double()
else:
    assert(False)

print(n,len(es))
for e in es:
    print(*e)

Solution (Python):
l = int(input())
ll = l
n = 0
while ll > 0:
    ll >>= 1
    n += 1
es = []
for i in range(n-1):
    es.append((i+1, i, 0))
    es.append((i+1, i, 1<<i))

ll = l
for i in range(n-1):
    if (ll>>i)&1 != 0:
        ll &= ll-1
        es.append((n-1, i, ll))

m = len(es)
print(n, m)
for e in es:
    print(n-e[0], n-e[1], e[2])

Solution (Python):
ll = int(input())
l = ll-1
bb = format(l,'b')
x = len(bb)-1

ans=[]

for i in range(x):
    ans.append((i+1,i+2,0))
    ans.append((i+1,i+2,2**(x-i-1)))

a = l - 2**x+1
acum=2**x

n=x+1

while a != 0:
    bb = format(a,'b')
    y = len(bb)-1
    if x+1-y == 1:
        ans.append((x+1,x+2,0))
        ans.append((x+1,x+2,2**x))
        n+=1
        a=0
    else:
        ans.append((1,x+1-y,acum))
        a = a-2**y
        acum += 2**y

m = len(ans)
print(n,m)

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

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(L):

    e = []
    n = 1
    l = L - 1

    r = math.floor(math.log(L, 2))
    for j in range(r):
        e.append((n, n+1, 0))
        e.append((n, n+1, 2**j))
        n += 1

    for t in range(n-1, 0, -1):
        if L - 2**(t-1) >= 2**r:
            e.append((t, n, L - 2**(t-1)))
            L -= 2**(t-1)

    print(n, len(e))
    for u, v, c in e:
        print(u, v, c)


def main():
    L = read_int()
    slv(L)


if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(L):

    e = []
    n = 1
    l = L - 1

    r = math.floor(math.log(L, 2))
    for j in range(r):
        e.append((n, n+1, 0))
        e.append((n, n+1, 2**j))
        n += 1

    for t in range(n-1, 0, -1):
        if L - 2**(t-1) >= 2**r:
            e.append((t, n, L - 2**(t-1)))
            L -= 2**(t-1)

    print(n, len(e))
    for u, v, c in e:
        print(u, v, c)


def main():
    L = read_int()
    slv(L)


if __name__ == '__main__':
    main()

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

xs = []

for m in range(21):
    if (2 << m) > L:
        break
    xs.append((m+1, m+2, 0))
    xs.append((m+1, m+2, 1 << m))

b = 1 << m

for i in range(m - 1, -1, -1):
    c = 1 << i
    if L - b >= c:
        xs.append((i + 1, m + 1, b))
        b += c

print(m + 1, len(xs))

for x in xs:
    print(*x)

Solution (Python):
def base3(K):
    if K<3:
        return str(K)
    else:
        return str(K%3)+base3(K//3)
L=int(input())
T=base3(L)
N=len(T)
A=[]
for i in range(N-1):
    tmp=3**i
    for k in range(3):
        A.append((i+1,i+2,k*tmp))
bef=0
for i in range(N)[::-1]:
    tmp=3**i
    for k in range(int(T[i])):
        A.append((i+1,N+1,bef+k*tmp))
    bef+=int(T[i])*tmp
print(N+1,len(A))
for p in A:
    print(p[0],p[1],p[2])

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

xs = []

for m in range(21):
    if (2 << m) > L:
        break
    xs.append((m+1, m+2, 0))
    xs.append((m+1, m+2, 1 << m))

b = 1 << m
x = L - b

for i in range(m - 1, -1, -1):
    c = 1 << i
    if x >= c:
        xs.append((i+1, m+1, b))
        x -= c
        b += c

print(m + 1, len(xs))

for x in xs:
    print(*x)

Solution (Python):
L = int(input())
R = 0
while True:
  R += 1
  if 2 ** R > L:
    R -= 1
    break
N = R + 1
M = 2 * R
_L = L
for r in range(R, 0, -1):
  if _L - 2 ** (r - 1) >= 2 ** R:
    M += 1
    _L -= 2 ** (r - 1)
print(N, M)
for i in range(R):
  print(i + 1, i + 2, 2 ** i)
  print(i + 1, i + 2, 0)
for r in range(R, 0, -1):
  if L - 2 ** (r - 1) >= 2 ** R:
    print(r, N, L - 2 ** (r - 1))
    L -= 2 ** (r - 1)

Solution (Python):



import array
from bisect import *
from collections import *
import fractions
import heapq 
from itertools import *
import math
import random
import re
import string
import sys

L = int(input())
orig_L = L

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


v_sink = v




n //= 2
N = n
L -= N





while L > 0:
    if L >= n:
        edges.append((v, v_sink, N))
        L -= n
        N += n
    n //= 2
    v -= 1

print(v_sink, len(edges))
for e in edges:
    print(*e)

Solution (Python):

 
L = int(input())

t = L
c = 0
zf = []
endd = []

tc = 1
while t>0:
    g = t%2
    c+= g
    zf.append(g)
    t//=2
    tc*=2
    endd.append(t*tc)
while len(zf)<20:
    zf.append(0)
 

lastd = False
if L >= 2**19:
    lastd = True
en = 36+c
if lastd:
    en+=1
print(20, en  )

x = 1
t = L
for i in range(1,20):
    if zf[i-1] == 1:
        print(i, 20, endd[i-1])
    if (i!=19 or lastd):
        print(i, i+1, 0)
        print(i, i+1, x) 
    x*=2

Solution (Python):
L=int(input())
s=bin(L)[2:]
l=len(s)-1
ans=[]
for i in range(l):
    ans.append([i+1,i+2,2**(l-i-1)])
    ans.append([i+1,i+2,0])
u=2**(l)
for k in range(1,l+1):
    if s[k]!='0':
        ans.append([1,k+1,u])
        u+=2**(l-k) 
        
print(l+1,len(ans))
for a,b,c in ans:
    print(a,b,c)

Solution (Python):
L = int(input())
B = []
for i in range(20):
    L, b = divmod(L, 2)
    B.append(b)
B.reverse()
f = False
E = []
s = 0
for i, b in enumerate(B[:19]):
    E.append([i+1, i+2, 0])
    if b==1:
        f = True

    if f:
        E.append([i+1, i+2, 2**(18-i)])

for i, b in enumerate(B):
    if b==1:
        if s!=0:
            E.append([1, i+1, s])
        s += 2 ** (19-i)

print(20, len(E))
for e in E:
    print(" ".join(map(str, e)))

Solution (Python):
import sys

L, = map(int, sys.stdin.readline().split())

N = 1
while True:
    if L < 2 ** N:
        break
    N += 1


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

i = N-1
m = 2 ** (N-1)
while i >= 1:
    a = 2**(i-1) - 1
    if a + m <= L-1:
        res.append((i, N, m))
        m = a+m+1
    i -= 1


print(N, len(res))
for i, j, d in res:
    print(i, j, d)

Solution (Python):
from sys import stdin, stdout
from collections import deque
from math import log10


l = int(stdin.readline())
n = 21
M = 0

vertices = [[] for i in range(n)]
cur = 2
f = 20
vl = 1
i = f - 1

while cur <= l:
    vertices[i].append((i + 1, 0))
    vertices[i].append((i + 1, vl))
    M += 2
    vl <<= 1
    cur <<= 1
    i -= 1

st = i + 1
cur >>= 1


while cur != l:
    lb, rb = st, f
    
    while rb - lb > 1:
        m = (lb + rb) >> 1
        
        if (1 << (f - m)) + cur <= l:
            rb = m
        else:
            lb = m
    
    vertices[st].append((rb, cur))
    cur = (1 << (f - rb)) + cur
    M += 1
    

stdout.write(str(f - st + 1) + ' ' + str(M) + '\n')
for i in range(st, f + 1):
    for v in vertices[i]:
        stdout.write(str(i - st + 1) + ' ' + str(v[0] - st + 1) + ' ' + str(v[1]) + '\n')

Solution (Python):
def base3(K):
    tmp=K
    S=""
    while(True):
        S=str(tmp%3)+S
        tmp=tmp//3
        if tmp==0:
            break
    return S
L=int(input())
T=base3(L)[::-1]
N=len(T)
A=[]
for i in range(N-1):
    tmp=3**i
    for k in range(3):
        A.append((i+1,i+2,k*tmp))
bef=0
for i in range(N)[::-1]:
    tmp=3**i
    for k in range(int(T[i])):
        A.append((i+1,N+1,bef+k*tmp))
    bef+=int(T[i])*tmp
print(N+1,len(A))
for p in A:
    print(p[0],p[1],p[2])

Solution (Python):
L = int(input())
N = L.bit_length()
res = L - (1 << (N - 1))
start = 1 << (N - 1)

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

for i in reversed(range(N)):
    if res >= (1 << i):
        ans.append((1, N - i, start))
        start += (1 << i)
        res -= 1 << i

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

Solution (Python):
l = int(input())
b3_list = []

k = 1
while l != 0:
	b3_list.append((l % (3 ** k)) // (3 ** (k - 1)))
	l -= l % (3 ** k)
	k += 1


digit = len(b3_list) 

n = digit + 1
edges = []
for i in range(1, digit):
	edges.append([i, i + 1, 0])
	edges.append([i, i + 1, 3 ** (i - 1)])
	edges.append([i, i + 1, 3 ** (i - 1) * 2])

if b3_list[-1] == 1:
	edges.append([digit, digit + 1, 0])

elif b3_list[-1] == 2:
	edges.append([digit, digit + 1, 0])
	edges.append([digit, digit + 1, 3 ** (digit - 1)])

for i in range(1, digit):
	base_num = 0
	for j in range(i, digit):
		base_num += b3_list[j] * (3 ** j)
	if b3_list[i - 1] == 0:
		continue
	elif b3_list[i - 1] == 1:
		edges.append([i, n, base_num])
	elif b3_list[i - 1] == 2:
		edges.append([i, n, base_num])
		edges.append([i, n, base_num + 3 ** (i - 1)])

m = len(edges)

print(n, m)
for i in range(m):
	print(*edges[i])

Solution (Python):
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

MAXN = 20

L = read()
Lb = [int(L & (1 << b) > 0) for b in range(MAXN)]

edges = []
for i in range(MAXN-2):
  edges.append((MAXN-1-i, MAXN-i, 0))
  edges.append((MAXN-1-i, MAXN-i, 1 << i))

def dec(bs):
  return sum(b * (1 << i) for i, b in enumerate(bs))

for i in range(MAXN-2):
  if Lb[i] == 1:
    w = dec(Lb[i+1:]) * 2**(i+1)
    edges.append((1, MAXN-i, w))

head = dec(Lb[MAXN-2:])
for bb in range(head):
  edges.append((1, 2, bb * 2**(MAXN-2)))

N = 20
M = len(edges)
print(N, M)
for u, v, w in edges:
  print(u, v, w)

Solution (Python):


import sys

L = int(input())

a=[]
i=L
m=0

a.append(i%4)
i-=i%4
i=i//4
while(i > 0):
    a.append(i%2)
    i=i//2
p=len(a)
n=p+1

ans=[]
for i in range(L%4):
    ans.append([1,n,L-1-i])


L=L//4

if L != 0:
    ans.append([n-1,n,0])
    ans.append([n-1,n,L])
    ans.append([n-1,n,L*2])
    ans.append([n-1,n,L*3])

j=1
while(L > 0):
    if L%2==1:
        ans.append([1,n-j,L-1])
    L=L//2
    if L != 0:
        ans.append([n-j-1,n-j,0])
        ans.append([n-j-1,n-j,L])
    j+=1




print(n,len(ans))
for i in ans:
    for j in i:
        print(j, end=" ")
    print()

Solution (Python):
l=int(input())-1
s=bin(l)[2:]
if s.count("0")==0:
    n=len(s)+1
    print(str(n)+" "+str(2*(n-1)))
    for i in range(n-1):
        print(str(i+1)+" "+str(i+2)+" 0")
        print(str(i+1)+" "+str(i+2)+" "+str(2**i))
else:
    n=len(s)
    res=""
    for i in range(n-1):
        res+=str(i+1)+" "+str(i+2)+" 0\n"
        res+=str(i+1)+" "+str(i+2)+" "+str(2**i)+"\n"
    while True:
        if s[-1]=="1":
            for i in range(1,n+1):
                if s[-i]=="0":
                    break
            ss=s[:-i]+"0"*i
            nnn=int(ss,2)
            res+=str(i)+" "+str(n)+" "+str(nnn)+"\n"
            s=bin(nnn-1)[2:]
            if len(s)<n:
                break
        else:
            res+="1 "+str(n)+" "+str(l)+"\n"
            if s.count("1")>1:
                s=bin(l-1)[2:]
            else:
                break
    r=res.count("\n")
    res=res[:-1]
    print(str(n)+" "+str(r))
    print(res)

Solution (Python):

import sys
try: from typing import Any, Union, List, Tuple, Dict
except ImportError: pass
sys.setrecursionlimit(10**6)
def debug(*args): print(*args, file=sys.stderr)
def exit(): sys.exit(0)


L = int(input())


def sanshin(x):
    res = []
    while x > 0:
        res.append(x % 3)
        x = x // 3
    return res


a = sanshin(L)
b = []
L_ = L
for i in range(len(a)):
    L_ -= a[i] * 3**i
    b.append(L_)

N = 14
result = []

for i in range(N-1):
    result.append((i, i+1, 0))
    result.append((i, i+1, 3**i))
    if 2*(3**i) < 10**6:
        result.append((i, i+1, 2*(3**i)))


for i in range(N):
    if i >= len(a):
        break
    if a[i] == 1:
        result.append((i, N, b[i]))
    elif a[i] == 2:
        result.append((i, N, b[i]))
        result.append((i, N, b[i] + 3**i))


M = len(result)
print(N+1, M)
for res in result:
    print(res[0]+1, res[1]+1, res[2])