Maximum profit earned on weighted un-directed tree
Firstly, use a PEP8 checker. It will raise a lot of issues about whitespace and also tell you to change


            if visited[k[0]-1] == False:



to either

            if visited[k[0]-1] is False:


or

            if not visited[k[0]-1]:




The DFS is far more complicated than necessary:


We don't need visited: given that we know that the graph is a tree, it suffices to track the previous vertex.
I'm used to DFS tracking vertices, not edges.
There's no reason for dfs to take profit as an argument: the profit that can be made in a rooted subtree is independent of the profit made getting there.


Rewriting with those notes in mind, we can reduce it to

    def start(self, power):
        return max(self.dfs(u, power, None) for u in range(1, self.nodes+1))

    def dfs(self, u, power, prev):
        return max((edge[2] + self.dfs(edge[0], power - edge[1], u)
                    for edge in self.graph[u]
                    if edge[0] != prev and edge[1] &lt;= power),
                   default=0)




However, I think this is still inefficient in some cases. It's doing \$n\$ depth-first searches, for overall time \$\Theta(n^2)\$. But those searches are traversing the same vertices. I believe (although I haven't written the code to verify it) that it should be possible to do it in \$\Theta(np)\$ where \$p\$ is the starting power. The idea would be to do one DFS, but for each subtree to return a complicated structure containing the largest score available solely within that subtree, and the largest scores available from the root of that subtree for different powers (which would obviously be monotonically increasing). Then it would be necessary to combine these.

(Floyd-Warshall is cubic time, so that would be worse. Similarly, matrix-based all-pairs-shortest-path algorithms for general graphs would be worse).