Minimum Upgrade Cost for Bridges

You are given a set of islands connected by bridges. Each bridge has an associated magical strength. In order to ensure the bridges meet a required safety standard, each bridge must have a magical strength of at least \(s_0\). For any bridge whose current strength \(s_i\) is less than \(s_0\), an upgrade is needed and the cost to upgrade that bridge is \(s_0 - s_i\). Your task is to calculate the total minimum cost to upgrade all the bridges so that their strengths are at least \(s_0\).

Input Format

The first line of input contains three integers \(n\), \(m\) and \(s_0\) where \(n\) is the number of islands, \(m\) is the number of bridges, and \(s_0\) is the required minimum magical strength for the bridges.

This is followed by \(m\) lines, each containing three integers \(a\), \(b\), \(s_i\), representing a bridge connecting island \(a\) and island \(b\) with current strength \(s_i\).

Output Format

Output a single integer, which is the total cost required to upgrade the bridges.

inputFormat

The input is read from standard input (stdin). The first line contains three space-separated integers \(n\), \(m\), and \(s_0\). Each of the next \(m\) lines contains three space-separated integers \(a\), \(b\), and \(s_i\), representing a bridge.

outputFormat

Output the total cost as a single integer to standard output (stdout).

3 3 8
1 2 5
2 3 7
3 1 6

6