Minimum Travel Cost with Discount

You are given a network of n cities connected by m bidirectional roads. Each road has an associated travel cost. Additionally, you are provided with a discount value d which reduces the cost of each road, i.e. the effective cost of a road is \(\max(c-d, 0)\). Your task is to compute the minimum travel cost between every pair of cities using these discounted road costs.

More formally, given:

• An integer \(n\): the number of cities.
• An integer \(m\): the number of roads.
• A list of \(m\) roads where each road is represented as a triplet \((a, b, c)\) meaning there is a bidirectional road between city \(a\) and city \(b\) with cost \(c\) (\(1 \leq c \leq 10^6\)).
• An integer \(d\) (\(0 \leq d \leq 10^6\)): the discount value applied to each road.

The effective cost of a road is computed as:

[ \text{effective cost} = \max(c-d, 0) ]

Your program should compute a cost matrix where the \(j\)th element of the \(i\)th row is the minimum travel cost from city \(i\) to city \(j\). You may assume that the roads provide enough connectivity so that any city is reachable from any other city.

inputFormat

The input is given from the standard input (stdin) in the following format:

n m d
a1 b1 c1
a2 b2 c2
... 
am bm cm

Where:

• The first line contains three space-separated integers: the number of cities \(n\), the number of roads \(m\), and the travel discount \(d\).
• Each of the following \(m\) lines contains three integers \(a\), \(b\), and \(c\), describing a road connecting city \(a\) and city \(b\) with travel cost \(c\).

outputFormat

The output should be printed to standard output (stdout) as \(n\) lines. Each line contains \(n\) space-separated integers representing the minimum travel cost from the corresponding city to every other city. The \(i\)th line corresponds to the \(i\)th city's minimum travel costs, and the \(j\)th number on that line is the minimum travel cost from city \(i\) to city \(j\).

## sample

2 1 5
1 2 10

0 5
5 0

</p>