Given a graph, a source vertex in the graph, and a number k, find if there is a simple path, of path length greater than or equal to k,(without any cycle) starting from a given source and ending at any other vertex.
Source vertex should always be  0.
Example 1:
Input:
V = 4 , E = 3 and K = 8
A[] = [0, 1, 5, 1, 2, 1, 2, 3, 1]
Output: 0
Explanation:
There exists no path which has a distance 
of 8. 
 
Example 2:
Input:
V = 9, E = 14 and K = 60
A[] = [0, 1, 4, 0, 7, 8, 1, 2, 8, 1, 7, 
11, 2, 3, 7, 2, 5, 4, 2, 8, 2, 3, 4, 9, 
3, 5, 14, 4, 5, 10, 5, 6, 2, 6, 7, 1, 6, 
8, 6, 7, 8, 7]
Output: 0
Explanation:
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function pathMoreThanK() which takes the integer V, Edges E, an integer K and Array A which is having (Source, Destination, Weight) as input parameters and returns 1 if the path of at least k distance exists, else returns 0.
Expected Time Complexity: O(N!)
Expected Auxiliary Space: O(N)
 
Constraints:
2 ≤ V ≤ 5
1 ≤ E ≤ 20
1 ≤ K ≤ 100

Difficulty: MEDIUM_HARD
Expected Time Complexity: O(N!)
Expected Auxiliary Space: O(N)

Starter code:

class Solution:
    def pathMoreThanK (self, V, E, K, A):
        # code here
        pass



Solutions:
from collections import defaultdict as dict

class Solution:

	def pathMoreThanK(self, V, E, K, A):
		adj = dict(list)
		for i in range(0, len(A), 3):
			adj[A[i]].append((A[i + 1], A[i + 2]))
			adj[A[i + 1]].append((A[i], A[i + 2]))
		pathVisited = set()

		def dfs(node, pathSum):
			pathVisited.add(node)
			if K <= pathSum:
				return True
			for (neib, neibwt) in adj[node]:
				if neib not in pathVisited:
					if dfs(neib, pathSum + neibwt):
						return True
			pathVisited.remove(node)
			return False
		src = 0
		if dfs(src, 0):
			return 1
		return 0


from collections import defaultdict

class Solution:

	def pathMoreThanK(self, V, E, K, A):
		graph = {i: [] for i in range(V)}
		for i in range(0, 3 * E, 3):
			(u, v, wt) = (A[i], A[i + 1], A[i + 2])
			graph[u].append([v, wt])
			graph[v].append([u, wt])
		visited = [0] * V

		def dfs(node, K, cost):
			if cost >= K:
				return True
			visited[node] = 1
			for nei in graph[node]:
				(v, wt) = (nei[0], nei[1])
				if not visited[v]:
					if dfs(v, K, cost + wt):
						return True
			visited[node] = 0
			return False
		return dfs(0, K, 0)


class Solution:

	def pathMoreThanK(self, v, e, k, a):
		adj = [[] for _ in range(v)]
		for i in range(0, 3 * e - 2, 3):
			adj[a[i]].append((a[i + 1], a[i + 2]))
			adj[a[i + 1]].append((a[i], a[i + 2]))
		visited = [0] * v
		visited[0] = 1

		def dfs(node, k, path):
			if path >= k:
				return True
			visited[node] = True
			for (next_node, next_dist) in adj[node]:
				if not visited[next_node]:
					if dfs(next_node, k, path + next_dist):
						return True
			visited[node] = False
			return False
		return dfs(0, k, 0)


from collections import defaultdict

class Solution:

	def pathMoreThanK(self, n, edges, k, adj):
		g = [[] for _ in range(n)]
		seen = [False] * n
		m = len(adj)
		for i in range(0, m, 3):
			(u, v, w) = (adj[i], adj[i + 1], adj[i + 2])
			g[u].append((v, w))
			g[v].append((u, w))

		def fun(u, k):
			if k <= 0:
				return True
			i = 0
			while i < len(g[u]):
				(v, w) = g[u][i]
				i += 1
				if seen[v]:
					continue
				if w >= k:
					return True
				seen[v] = True
				if fun(v, k - w):
					return True
				seen[v] = False
			return False
		seen[0] = True
		return 1 if fun(0, k) else 0


class Solution:

	def pathMoreThanK(self, V, E, K, A):
		self.adj = [[] for _ in range(V)]
		for i in range(E):
			self.adj[A[3 * i]].append([A[3 * i + 1], A[3 * i + 2]])
			self.adj[A[3 * i + 1]].append([A[3 * i], A[3 * i + 2]])
		self.k = K
		return self.func([0], 0, {0: True})

	def func(self, curPath, curLength, visited):
		if curLength >= self.k:
			return True
		lastNode = curPath[-1]
		for (v, w) in self.adj[lastNode]:
			if v not in visited:
				visited[v] = True
				if self.func(curPath + [v], curLength + w, visited):
					return True
				visited.pop(v)
		return False


class Solution:

	def dfs(self, node, graph, vis, k, cost):
		if cost >= k:
			return 1
		vis[node] = True
		for i in graph[node]:
			(v, wt) = (i[0], i[1])
			if not vis[v]:
				if self.dfs(v, graph, vis, k, cost + wt):
					return 1
		vis[node] = False
		return 0

	def pathMoreThanK(self, V, E, K, A):
		graph = {}
		for i in range(V):
			graph[i] = []
		for i in range(0, 3 * E, 3):
			(u, v, wt) = (A[i], A[i + 1], A[i + 2])
			graph[u].append([v, wt])
			graph[v].append([u, wt])
		vis = [False for i in range(V)]
		return self.dfs(0, graph, vis, K, 0)


class Graph:

	def __init__(self, V):
		self.V = V
		self.adj = [[] for i in range(V)]

	def add_edge(self, u, v, w):
		self.adj[u].append([v, w])
		self.adj[v].append([u, w])

class Solution:

	def util(self, src, path, adj, K):
		if K <= 0:
			return True
		for i in adj[src]:
			node = i[0]
			weight = i[1]
			if not path[node]:
				path[node] = True
				if self.util(node, path, adj, K - weight):
					return True
				path[node] = False
		return False

	def pathMoreThanK(self, V, E, K, A):
		adj = [[] for i in range(V)]
		for i in range(0, len(A), 3):
			u = A[i]
			v = A[i + 1]
			w = A[i + 2]
			adj[u].append((v, w))
			adj[v].append((u, w))
		path = [False] * V
		src = 0
		path[0] = True
		return self.util(src, path, adj, K)


class Solution:

	def create(self, arr, V):
		graph = [[] for i in range(V)]
		i = 0
		while i < len(arr) - 2:
			graph[arr[i]].append([arr[i + 1], arr[i + 2]])
			graph[arr[i + 1]].append([arr[i], arr[i + 2]])
			i += 3
		return graph

	def dfs(self, graph, node, k):
		vis[node] = 1
		for j in graph[node]:
			if k <= 0:
				return True
			adj = j[0]
			dist = j[1]
			if vis[adj]:
				continue
			if self.dfs(graph, adj, k - dist):
				return True
		vis[node] = 0
		return False

	def pathMoreThanK(self, V, E, k, arr):
		graph = self.create(arr, V)
		global vis
		vis = [0 for i in range(V)]
		return self.dfs(graph, 0, k)


from collections import defaultdict

class Solution:

	def pathMoreThanK(self, v, e, k, A):
		adj = defaultdict(list)
		for i in range(0, len(A), 3):
			adj[A[i]].append([A[i + 1], A[i + 2]])
			adj[A[i + 1]].append([A[i], A[i + 2]])
		visited = [0] * v

		def dfs(node, path):
			nonlocal visited
			visited[node] = 1
			if path >= k:
				return True
			for (ngbhr, weight) in adj[node]:
				if visited[ngbhr] == 0:
					if dfs(ngbhr, path + weight):
						return True
			visited[node] = 0
			return False
		res = dfs(0, 0)
		return res


import collections

class Solution:

	def pathMoreThanK(self, V, E, K, A):
		g = collections.defaultdict(list)
		for i in range(0, len(A), 3):
			(a, b, w) = (A[i], A[i + 1], A[i + 2])
			g[a].append([b, w])
			g[b].append([a, w])
		sz = dfs(0, g, set())
		return sz >= K

def dfs(n, g, v):
	v.add(n)
	sz = 0
	for (nei, w) in g[n]:
		if nei not in v:
			sz = max(sz, w + dfs(nei, g, v))
	v.remove(n)
	return sz


from collections import defaultdict

class Solution:

	def check(self, graph, n, vis, s, k, length):
		if length >= k:
			return True
		vis[s] = 1
		for i in range(n):
			if i != s and graph[s][i] > 0 and (vis[i] == 0):
				if self.check(graph, n, vis, i, k, length + graph[s][i]):
					return True
		vis[s] = 0
		return False

	def pathMoreThanK(self, n, e, k, arr):
		graph = [[0 for i in range(n)] for _ in range(n)]
		i = 0
		while i + 2 < len(arr):
			graph[arr[i]][arr[i + 1]] = max(arr[i + 2], graph[arr[i]][arr[i + 1]])
			graph[arr[i + 1]][arr[i]] = max(arr[i + 2], graph[arr[i]][arr[i + 1]])
			i += 3
		vis = [0] * n
		return 1 if self.check(graph, n, vis, 0, k, 0) == True else 0


from collections import *

class Solution:

	def pathMoreThanK(self, n, m, k, arr):
		graph = defaultdict(list)
		visited = set()
		ans = [False]
		for i in range(m):
			(p, q, d) = (arr[3 * i], arr[3 * i + 1], arr[3 * i + 2])
			graph[p].append([q, d])
			graph[q].append([p, d])

		def rec(node, d):
			if ans[0]:
				return
			if d >= k:
				ans[0] = True
				return
			visited.add(node)
			for (nnode, dist) in graph[node]:
				if nnode not in visited:
					rec(nnode, dist + d)
			visited.remove(node)
		rec(0, 0)
		return ans[0]


from collections import defaultdict
import heapq

class Solution:

	def dfs(self, src, d, visited, target):
		if target <= 0:
			return True
		visited[src] = True
		for (nbr, wt) in d[src]:
			if not visited[nbr]:
				ans = self.dfs(nbr, d, visited, target - wt)
				if ans:
					return True
		visited[src] = False
		return False

	def pathMoreThanK(self, v, e, k, A):
		d = defaultdict(list)
		for i in range(0, len(A), 3):
			d[A[i]].append([A[i + 1], A[i + 2]])
			d[A[i + 1]].append([A[i], A[i + 2]])
		visited = [0] * v
		ans = self.dfs(0, d, visited, k)
		if ans:
			return 1
		return 0


from collections import defaultdict

class Solution:

	def pathMoreThanK(self, V, E, K, A):
		graph = defaultdict(list)
		for i in range(0, len(A), 3):
			graph[A[i]].append((A[i + 1], A[i + 2]))
			graph[A[i + 1]].append((A[i], A[i + 2]))
		sum = 0
		self.ans = 0
		vis = set()

		def dfs(node, sum):
			if sum >= K:
				self.ans = 1
				return
			if node not in vis:
				vis.add(node)
			for (n, c) in graph[node]:
				if n not in vis:
					vis.add(n)
					sum += c
					dfs(n, sum)
					sum -= c
					vis.remove(n)
		dfs(0, 0)
		return self.ans


class Solution:

	def dfs(self, u, adj, visited, k):
		visited[u] = True
		if k <= 0:
			return True
		for (v, w) in adj[u]:
			if visited[v]:
				continue
			if self.dfs(v, adj, visited, k - w):
				return True
		visited[u] = False
		return False

	def pathMoreThanK(self, V, E, k, A):
		adj = {i: [] for i in range(V)}
		for i in range(E):
			u = A[3 * i]
			v = A[3 * i + 1]
			w = A[3 * i + 2]
			adj[u].append([v, w])
			adj[v].append([u, w])
		visited = [False] * V
		return self.dfs(0, adj, visited, k)


def pathMoreThanKUtil(graph, sourceVertex, path, k):
	if k <= 0:
		return True
	for i in range(len(graph[sourceVertex])):
		v = graph[sourceVertex][i][0]
		w = graph[sourceVertex][i][1]
		if path[v] == True:
			continue
		if w > k:
			return True
		path[v] = True
		if pathMoreThanKUtil(graph, v, path, k - w):
			return True
		path[v] = False
	return False

def pathMoreThanK1(n, m, k, edges):
	sourceVertex = 0
	adj = [[] for i in range(n)]
	for i in range(0, len(edges), 3):
		v1 = edges[i]
		v2 = edges[i + 1]
		w = edges[i + 2]
		adj[v1].append([v2, w])
		adj[v2].append([v1, w])
	path = [False] * n
	path[sourceVertex] = True
	if pathMoreThanKUtil(adj, sourceVertex, path, k):
		return 1
	else:
		return 0

class Solution:

	def pathMoreThanK(self, V, E, K, A):
		return pathMoreThanK1(V, E, K, A)


from collections import defaultdict

class Solution:

	def recurse(self, src, k, adj, vis):
		vis[src] = 1
		if k <= 0:
			return True
		for (u, w) in adj[src]:
			if vis[u] == 1:
				continue
			if w >= k:
				return True
			if self.recurse(u, k - w, adj, vis):
				return True
		vis[src] = 0
		return False

	def pathMoreThanK(self, V, E, K, A):
		vis = [0 for _ in range(V + 1)]
		adj = defaultdict(list)
		for i in range(0, len(A), 3):
			(x, y, w) = (A[i], A[i + 1], A[i + 2])
			adj[x].append([y, w])
			adj[y].append([x, w])
		return self.recurse(0, K, adj, vis)


from math import inf

class Solution:

	def __pathMoreThanKHelper(self, curr_node, path_sum, graph, k):
		self.visited.add(curr_node)
		for (next_node, weight) in graph[curr_node]:
			if next_node not in self.visited:
				if path_sum + weight >= k:
					return 1
				if self.__pathMoreThanKHelper(next_node, path_sum + weight, graph, k) == 1:
					return 1
		self.visited.discard(curr_node)
		return 0

	def pathMoreThanK(self, v, e, k, a):
		(graph, self.visited) = ([[] for i in range(v)], set())
		for i in range(0, len(a) - 2, 3):
			graph[a[i]].append([a[i + 1], a[i + 2]])
			graph[a[i + 1]].append([a[i], a[i + 2]])
		return self.__pathMoreThanKHelper(0, 0, graph, k)


class Solution:

	def pathMoreThanK(self, V, E, K, A):

		def dfs(node, cost):
			visited[node] = True
			if cost >= K:
				return True
			for (destination, price) in adj[node]:
				if visited[destination] == False:
					if dfs(destination, cost + price) == True:
						return True
			visited[node] = False
			return 0
		visited = [False] * V
		adj = [[] for i in range(V)]
		for i in range(0, len(A), 3):
			adj[A[i]].append([A[i + 1], A[i + 2]])
			adj[A[i + 1]].append([A[i], A[i + 2]])
		cost = 0
		return dfs(0, cost) == True


class Solution:

	def pathMoreThanK(self, V, E, K, A):
		adj = [[] for i in range(V)]
		for i in range(0, len(A), 3):
			adj[A[i]].append([A[i + 1], A[i + 2]])
			adj[A[i + 1]].append([A[i], A[i + 2]])

		def dfs(node, adj, visited, K, cost):
			visited[node] = True
			if cost >= K:
				return True
			for (end, distance) in adj[node]:
				if visited[end] == False:
					if dfs(end, adj, visited, K, cost + distance) == True:
						return True
			visited[node] = False
		distance = 0
		visited = [False] * V
		if dfs(0, adj, visited, K, 0) == True:
			return True
		return False
		pass


import collections

class Solution:

	def pathMoreThanK(self, v, edges, k, arr):
		res = [0]

		def dfs(node, dist):
			res[0] = max(res[0], dist)
			if visited[node]:
				return
			visited[node] = True
			for nei in adj[node]:
				if not visited[nei[0]]:
					dfs(nei[0], dist + nei[1])
			visited[node] = False
		adj = {}
		for i in range(v):
			adj[i] = []
		i = 0
		visited = [False] * v
		while i < len(arr) - 2:
			adj[arr[i]].append([arr[i + 1], arr[i + 2]])
			adj[arr[i + 1]].append([arr[i], arr[i + 2]])
			i = i + 3
		dfs(0, 0)
		return 1 if res[0] >= k else 0


class Solution:

	def dfs(self, node, k, present_length):
		if present_length >= k:
			self.found = True
			return
		self.dfs_array[node] = 1
		for (child, dist) in self.adj[node]:
			if self.dfs_array[child] == 1:
				continue
			self.dfs(child, k, present_length + dist)
		self.dfs_array[node] = 0
		return

	def pathMoreThanK(self, V, E, K, A):
		self.dfs_array = [0 for _ in range(V)]
		self.adj = dict()
		for i in range(V):
			self.adj[i] = []
		for i in range(E):
			(x, y, wt) = (A[3 * i], A[3 * i + 1], A[3 * i + 2])
			self.adj[x].append([y, wt])
			self.adj[y].append([x, wt])
		self.found = False
		self.dfs(0, K, 0)
		return self.found


import math

class Solution:

	def pathMoreThanK(self, n, E, K, A):
		adj = [[] for i in range(n)]
		k = 0
		for i in range(E):
			(u, v, w) = A[k:k + 3]
			adj[u].append([v, w])
			adj[v].append([u, w])
			k += 3
		vis = [0 for i in range(n)]

		def maxDis(src, dst):
			if src == dst:
				return 0
			temp = 0
			for (ad, w) in adj[src]:
				if vis[ad] == 0:
					vis[ad] = 1
					temp = max(temp, w + maxDis(ad, dst))
					vis[ad] = 0
			return temp
		for i in range(1, n):
			vis[0] = 1
			temp = maxDis(0, i)
			if temp >= K:
				return True
		return False


def solve(idx, a, visited, k):
	if k <= 0:
		return True
	for i in a[idx]:
		if visited[i[0]] == 1:
			continue
		visited[i[0]] = 1
		if solve(i[0], a, visited, k - i[1]):
			return True
		visited[i[0]] = 0
	return False

class Solution:

	def pathMoreThanK(self, V, E, K, A):
		dic = {0: []}
		for i in range(0, len(A), 3):
			if A[i] not in dic:
				dic[A[i]] = [(A[i + 1], A[i + 2])]
			else:
				dic[A[i]].append((A[i + 1], A[i + 2]))
			if A[i + 1] not in dic:
				dic[A[i + 1]] = [(A[i], A[i + 2])]
			else:
				dic[A[i + 1]].append((A[i], A[i + 2]))
		visited = [0 for i in range(V)]
		visited[0] = 1
		ans = solve(0, dic, visited, K)
		return ans


class Solution:

	def create(self, arr, n, m):
		graph = [[] for i in range(n)]
		i = 0
		while i < len(arr):
			graph[arr[i]].append([arr[i + 1], arr[i + 2]])
			graph[arr[i + 1]].append([arr[i], arr[i + 2]])
			i += 3
		return graph

	def dfs(self, graph, i, k):
		vis[i] = 1
		if k <= 0:
			return True
		for j in graph[i]:
			v = j[0]
			wt = j[1]
			if vis[v] == 1:
				continue
			if wt >= k:
				return True
			if vis[v] == 0:
				if self.dfs(graph, v, k - wt):
					return True
		vis[i] = 0
		return False

	def pathMoreThanK(self, n, m, k, arr):
		graph = self.create(arr, n, m)
		global vis
		vis = [0 for i in range(n)]
		return self.dfs(graph, 0, k)


class Solution:

	def pathMoreThanK(self, V, E, K, A):
		graph = [[] for i in range(V)]
		for i in range(0, len(A), 3):
			graph[A[i]].append([A[i + 1], A[i + 2]])
			graph[A[i + 1]].append([A[i], A[i + 2]])
		vis = [False] * V

		def solve(vis, graph, node, k):
			vis[node] = True
			for adj in graph[node]:
				nextNode = adj[0]
				newWeight = adj[1]
				if vis[nextNode] == True:
					continue
				if newWeight >= k:
					return True
				if solve(vis, graph, nextNode, k - newWeight):
					return True
			vis[node] = False
			return False
		return solve(vis, graph, 0, K)


class Solution:

	def pathMoreThanK(self, V, E, K, A):
		adj = [[] for i in range(V)]
		vis = [False] * V
		for i in range(E):
			(a, b, c) = A[3 * i:3 * i + 3]
			adj[a].append([b, c])
			adj[b].append([a, c])

		def path(node, curr_sum, K):
			if curr_sum >= K:
				return True
			vis[node] = True
			for (a, wt) in adj[node]:
				if vis[a] == True:
					continue
				elif path(a, curr_sum + wt, K):
					return True
			vis[node] = False
			return False
		return 1 if path(0, 0, K) else 0


class Solution:

	def pathMoreThanK(self, V, E, K, A):
		adj = {x: [] for x in range(V)}
		for i in range(0, len(A) - 2, 3):
			adj[A[i]].append((A[i + 1], A[i + 2]))
			adj[A[i + 1]].append((A[i], A[i + 2]))
		vis = [False] * V
		vis[0] = True

		def sol(i=0):
			ans = 0
			for (nei, w) in adj[i]:
				if vis[nei]:
					continue
				vis[nei] = True
				ans = max(ans, w + sol(nei))
				vis[nei] = False
			return ans
		if sol(0) >= K:
			return True
		return False


from collections import defaultdict

class Solution:

	def pathMoreThanK(self, V, E, K, A):
		graph = defaultdict(list)
		i = 0
		while i <= len(A) - 3:
			graph[A[i]].append((A[i + 1], A[i + 2]))
			graph[A[i + 1]].append((A[i], A[i + 2]))
			i += 3

		def dfs(i, K, visited):
			if K <= 0:
				return True
			visited[i] = True
			for (nei, d) in graph[i]:
				if visited[nei]:
					continue
				if d >= K:
					return True
				if not visited[nei]:
					if dfs(nei, K - d, visited):
						return True
				visited[nei] = False
			return False
		visited = [False] * V
		return dfs(0, K, visited)


from collections import defaultdict

class Solution:

	def pathMoreThanK(self, V, E, K, A):
		graph = defaultdict(list)
		i = 0
		while i <= len(A) - 3:
			graph[A[i]].append((A[i + 1], A[i + 2]))
			graph[A[i + 1]].append((A[i], A[i + 2]))
			i += 3

		def dfs(i, K, visited):
			if K <= 0:
				return True
			visited[i] = True
			for (nei, d) in graph[i]:
				if visited[nei]:
					continue
				if d >= K:
					return True
				if not visited[nei]:
					if dfs(nei, K - d, visited):
						return True
				visited[nei] = False
			return False
		visited = [False] * V
		return dfs(0, K, visited)
if __name__ == '__main__':
	ob = Solution()
	t = int(input())
	for _ in range(t):
		(V, E, K) = map(int, input().split())
		A = list(map(int, input().split()))
		ans = ob.pathMoreThanK(V, E, K, A)
		if ans:
			print(1)
		else:
			print(0)


class Solution:

	def pathMoreThanK(self, V, E, K, A):
		graph = []
		for a in range(V):
			graph.append([])
		for b in range(0, len(A), 3):
			x = A[b + 0]
			y = A[b + 1]
			weight = A[b + 2]
			graph[x].append([y, weight])
			graph[y].append([x, weight])
		visited = [0] * V

		def dfs(s, k):
			if k <= 0:
				return True
			visited[s] = 1
			for j in range(len(graph[s])):
				if visited[graph[s][j][0]] == 0:
					we = graph[s][j][1]
					k -= we
					if dfs(graph[s][j][0], k):
						return True
					k += we
			visited[s] = 0
			return False
		if dfs(0, K):
			return True
		else:
			return False
if __name__ == '__main__':
	ob = Solution()
	t = int(input())
	for _ in range(t):
		(V, E, K) = map(int, input().split())
		A = list(map(int, input().split()))
		ans = ob.pathMoreThanK(V, E, K, A)
		if ans:
			print(1)
		else:
			print(0)


class Solution:

	def pathMoreThanK(self, V, E, K, A):
		adj = [[] for i in range(V)]
		for i in range(0, 3 * E, 3):
			adj[A[i]].append([A[i + 1], A[i + 2]])
			adj[A[i + 1]].append([A[i], A[i + 2]])
		visited = [0] * V
		visited[0] = 1

		def dfs(source, k):
			if k <= 0:
				return True
			i = 0
			while i != len(adj[source]):
				v = adj[source][i][0]
				w = adj[source][i][1]
				i = i + 1
				if visited[v] == 1:
					continue
				if w >= K:
					return True
				visited[v] = 1
				if dfs(v, k - w):
					return True
				visited[v] = 0
			return False
		return dfs(0, K)


from collections import defaultdict

class Solution:

	def pathMoreThanK(self, V, E, K, A):
		graph = defaultdict(list)
		n = len(A)
		i = 0
		while i < n:
			graph[A[i]].append((A[i + 1], A[i + 2]))
			graph[A[i + 1]].append((A[i], A[i + 2]))
			i += 3

		def dfs(node, k):
			visit[node] = 1
			if k <= 0:
				return True
			for (adj, val) in graph[node]:
				if visit[adj]:
					continue
				if val >= k:
					return True
				if dfs(adj, k - val):
					return True
			visit[node] = 0
			return False
		visit = defaultdict(int)
		return dfs(0, K)


class Solution:

	def pathMoreThanK(self, V, E, K, A):
		adj = [[] for i in range(V)]
		for i in range(0, 3 * E, 3):
			adj[A[i]].append([A[i + 1], A[i + 2]])
			adj[A[i + 1]].append([A[i], A[i + 2]])

		def dfs(adj, v, visit, k):
			visit[v] = True
			if k <= 0:
				return True
			for u in adj[v]:
				if visit[u[0]]:
					continue
				if u[1] >= k:
					return True
				if dfs(adj, u[0], visit, k - u[1]):
					return True
			visit[v] = False
			return False
		visit = [False] * V
		return dfs(adj, 0, visit, K)
		pass


class Solution:

	def pathMoreThanK(self, V, E, K, A):
		adj = [[] for i in range(V)]
		for i in range(0, 3 * E, 3):
			temp = 0
			if A[i] == A[i + 1]:
				continue
			for j in adj[A[i]]:
				if j[0] == A[i + 1]:
					if A[i + 2] > j[1]:
						j[1] = A[i + 2]
						for j in adj[A[i + 1]]:
							if j[0] == A[i]:
								j[1] = A[i + 2]
								break
					temp = 1
					break
			if temp == 0:
				adj[A[i]].append([A[i + 1], A[i + 2]])
				adj[A[i + 1]].append([A[i], A[i + 2]])
		global flag
		flag = 0

		def dfs(vertex, cost, parent):
			global flag
			if cost >= K:
				flag = 1
				return
			for (v, w) in adj[vertex]:
				if v == parent:
					continue
				if color[v] == 'G':
					continue
				color[v] = 'G'
				dfs(v, cost + w, vertex)
				if flag == 1:
					break
			color[vertex] = 'W'
			return
		color = ['W' for i in range(V)]
		color[0] = 'G'
		dfs(0, 0, -1)
		return flag


class Solution:

	def pathMoreThanK(self, V, E, K, A):
		graph = [[] for i in range(V)]
		pt = 0
		for i in range(E):
			graph[A[pt]].append([A[pt + 1], A[pt + 2]])
			graph[A[pt + 1]].append([A[pt], A[pt + 2]])
			pt += 3
		self.visited = [0] * V

		def solve(node, cost):
			if cost >= K:
				return True
			self.visited[node] = 1
			for (nex, val) in graph[node]:
				if not self.visited[nex]:
					if solve(nex, cost + val):
						return True
			self.visited[node] = 0
			return False
		return solve(0, 0)


from math import inf

class Solution:

	def __pathMoreThanKHelper(self, root, path, graph, v, k):
		self.visited.add(root)
		for child in range(v):
			if child not in self.visited and graph[root][child] != -inf:
				if path + graph[root][child] >= k:
					return 1
				if self.__pathMoreThanKHelper(child, path + graph[root][child], graph, v, k) == 1:
					return 1
		self.visited.discard(root)
		return 0

	def pathMoreThanK(self, v, e, k, a):
		(graph, self.visited) = ([[-inf for i in range(v)] for j in range(v)], set())
		for i in range(0, len(a), 3):
			graph[a[i]][a[i + 1]] = max(graph[a[i]][a[i + 1]], a[i + 2])
			graph[a[i + 1]][a[i]] = max(graph[a[i + 1]][a[i]], a[i + 2])
		return self.__pathMoreThanKHelper(0, 0, graph, v, k)