Problem: Niwel is a little golden bear. As everyone knows, bears live in forests, but Niwel got tired of seeing all the trees so he decided to move to the city.

In the city, Niwel took on a job managing bears to deliver goods. The city that he lives in can be represented as a directed graph with n nodes and m edges. Each edge has a weight capacity. A delivery consists of a bear carrying weights with their bear hands on a simple path from node 1 to node n. The total weight that travels across a particular edge must not exceed the weight capacity of that edge.

Niwel has exactly x bears. In the interest of fairness, no bear can rest, and the weight that each bear carries must be exactly the same. However, each bear may take different paths if they like.

Niwel would like to determine, what is the maximum amount of weight he can deliver (it's the sum of weights carried by bears). Find the maximum weight.

Input

The first line contains three integers n, m and x (2 ≤ n ≤ 50, 1 ≤ m ≤ 500, 1 ≤ x ≤ 100 000) — the number of nodes, the number of directed edges and the number of bears, respectively.

Each of the following m lines contains three integers ai, bi and ci (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ ci ≤ 1 000 000). This represents a directed edge from node ai to bi with weight capacity ci. There are no self loops and no multiple edges from one city to the other city. More formally, for each i and j that i ≠ j it's guaranteed that ai ≠ aj or bi ≠ bj. It is also guaranteed that there is at least one path from node 1 to node n.

Output

Print one real value on a single line — the maximum amount of weight Niwel can deliver if he uses exactly x bears. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct if <image>.

Examples

Input

4 4 3
1 2 2
2 4 1
1 3 1
3 4 2


Output

1.5000000000


Input

5 11 23
1 2 3
2 3 4
3 4 5
4 5 6
1 3 4
2 4 5
3 5 6
1 4 2
2 5 3
1 5 2
3 2 30


Output

10.2222222222

Note

In the first sample, Niwel has three bears. Two bears can choose the path <image>, while one bear can choose the path <image>. Even though the bear that goes on the path <image> can carry one unit of weight, in the interest of fairness, he is restricted to carry 0.5 units of weight. Thus, the total weight is 1.5 units overall. Note that even though Niwel can deliver more weight with just 2 bears, he must use exactly 3 bears on this day.

Solution (in JAVA):

Solution:
import static java.lang.Math.max;
import static java.lang.Math.min;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashSet;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;


public class CFProblemD {

	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		int n = input.nextInt();
		int m = input.nextInt();
		int x = input.nextInt();
		int[][] capacity = new int[n][n];
		for (int a = 0; a < m; a++) {
			int start = input.nextInt() - 1;
			int end = input.nextInt() - 1;
			capacity[start][end] = input.nextInt();
		}
		// binarySearch for the weight each bear can carry.
		double lowerBound = 0.0;
		double upperBound = 1000000.0;
		double maxFlow = 100;
		while (upperBound - lowerBound > (lowerBound + (upperBound-lowerBound)*.5)/10E9) {
			double test = lowerBound + (upperBound-lowerBound)*.5;
			MaxFlowSolver solve = new Dinic(n);
			for (int a = 0; a < n; a++) {
				for (int b = 0; b < n; b++) {
					if (((int) (capacity[a][b] / test)) > 0) {
						solve.link(a, b, (int) (capacity[a][b] / test));
					}
				}
			}
			maxFlow = solve.getMaxFlow(solve.nodes.get(0),
					solve.nodes.get(n - 1));
			if (maxFlow >= x) {
				// bears were carrying too little;
				lowerBound = test;
			} else {
				upperBound = test;
			}
		}
		System.out.println(lowerBound*x);
	}

	// MAXFLOW2016
	static class Node {
		// thou shall not create nodes except through addNode()
		private Node() {
		}

		List<Edge> edges = new ArrayList<Edge>();
		int index; // index in nodes array
	}

	static class Edge {
		boolean forward; // true: edge is in original graph
							// false: edge is a backward edge
		Node from, to; // nodes connected
		int flow; // current flow
		int capacity;
		Edge dual; // reference to this edge's dual
		long cost; // only used for MinCost.

		// thou shall not create edges except through link()
		protected Edge(Node s, Node d, int c, boolean f) {
			forward = f;
			from = s;
			to = d;
			capacity = c;
		}

		// remaining capacity()
		int remaining() {
			return capacity - flow;
		}

		// increase flow and adjust dual
		void addFlow(int amount) {
			flow += amount;
			dual.flow -= amount;
		}
	}

	/* A Max Flow solver base class. */
	static abstract class MaxFlowSolver {
		/* List of nodes, indexed. */
		List<Node> nodes = new ArrayList<Node>();

		/* Create an edge between nodes n1 and n2 */
		void link(Node n1, Node n2, int capacity) {
			Edge e12 = new Edge(n1, n2, capacity, true);
			Edge e21 = new Edge(n2, n1, 0, false);
			e12.dual = e21;
			e21.dual = e12;
			n1.edges.add(e12);
			n2.edges.add(e21);
		}

		/* Create an edge between nodes n1 and n2 and assign cost */
		void link(Node n1, Node n2, int capacity, long cost) {
			Edge e12 = new Edge(n1, n2, capacity, true);
			Edge e21 = new Edge(n2, n1, 0, false);
			e12.dual = e21;
			e21.dual = e12;
			n1.edges.add(e12);
			n2.edges.add(e21);
			e12.cost = cost;
			e21.cost = -cost;
		}

		/* Create an edge between nodes n1 and n2 */
		void link(int n1, int n2, int capacity) {
			link(nodes.get(n1), nodes.get(n2), capacity);
		}

		/* Create a graph with n nodes. */
		protected MaxFlowSolver(int n) {
			for (int i = 0; i < n; i++)
				addNode();
		}

		protected MaxFlowSolver() {
			this(0);
		}

		abstract int getMaxFlow(Node src, Node snk);

		/* Add a new node. */
		Node addNode() {
			Node n = new Node();
			n.index = nodes.size();
			nodes.add(n);
			return n;
		}

		/*
		 * OPTIONAL: Returns the edges associated with the Min Cut. Must be run
		 * immediately after a getMaxFlow() call.
		 */
		List<Edge> getMinCut(Node src) {
			Queue<Node> bfs = new ArrayDeque<Node>();
			Set<Node> visited = new HashSet<Node>();
			bfs.offer(src);
			visited.add(src);
			while (!bfs.isEmpty()) {
				Node u = bfs.poll();
				for (Edge e : u.edges) {
					if (e.remaining() > 0 && !visited.contains(e.to)) {
						visited.add(e.to);
						bfs.offer(e.to);
					}
				}
			}
			List<Edge> minCut = new ArrayList<Edge>();
			for (Node s : visited) {
				for (Edge e : s.edges)
					if (e.forward && !visited.contains(e.to))
						minCut.add(e);
			}
			return minCut;
		}

		/*
		 * OPTIONAL: for min-cost, Klein's cycle canceling algorithm. Must be
		 * run after getMaxFlow() call. Given any max flow (with edge costs),
		 * cancel negative cycles until the flow is a min-cost max-flow.
		 * According to CS226 slides, this is O(E^2 C U) where C and U are max
		 * cost and capacity, respectively.
		 * 
		 * @return total cost of flow
		 */
		long minimizeFlow(Node src) {
			final long SUITABLE_INF = Long.MAX_VALUE / 2 - 1;

			// While there are negative cycles
			while (true) {

				// Find a negative cycle (sparse Bellman-Ford)
				// Initialize the graph
				int V = nodes.size();
				long[] dist = new long[V];
				Node[] pred = new Node[V];
				Arrays.fill(dist, SUITABLE_INF);
				dist[src.index] = 0;

				// Run up to V times
				boolean change = true;
				for (int i = 0; change && i < V; i++) {
					change = false;
					// For each (u, v) edge, try to relax
					for (Node from : nodes) {
						for (Edge e : from.edges) {
							if (e.remaining() == 0) {
								continue;
							}
							Node to = e.to;
							if (dist[from.index] + e.cost < dist[to.index]) {
								change = true;
								dist[to.index] = dist[from.index] + e.cost;
								pred[to.index] = from;
							}
						}
					}
				}

				// Find a negative-weight cycle
				ArrayList<Node> cycle = null;
				for (Node startingNode : nodes) {
					boolean[] seen = new boolean[V];
					Node currNode = startingNode;
					while (pred[currNode.index] != null
							&& !seen[currNode.index]) {
						seen[currNode.index] = true;
						currNode = pred[currNode.index];
					}
					if (pred[currNode.index] == null) {
						continue;
					}

					Node endNode = currNode;
					cycle = new ArrayList<Node>();
					while (true) {
						cycle.add(currNode);
						currNode = pred[currNode.index];
						if (currNode == endNode) {
							break;
						}
					}
				}

				// If there's no negative weight cycle, we're done
				if (cycle == null) {
					break;
				}

				// Get a list of edges in the cycle
				ArrayList<Edge> edgeCycle = new ArrayList<Edge>();
				for (int i = 0; i < cycle.size(); i++) {
					Node to = cycle.get(i);
					Node from = cycle.get((i + 1) % cycle.size());
					for (Edge e : from.edges) {
						if (e.to == to) {
							edgeCycle.add(e);
							break;
						}
					}
				}

				// Find the minimum residual capacity in the cycle
				int minResidual = Integer.MAX_VALUE;
				for (Edge e : edgeCycle) {
					minResidual = Math.min(minResidual, e.remaining());
				}

				if (minResidual == 0) {
					break;
				}

				// Add this flow to every edge on the cycle
				for (Edge e : edgeCycle) {
					e.addFlow(minResidual);
				}
			}

			return calcFlowCost();
		}

		// Calculate the cost of a flow, assuming that edge costs are given in
		// the network.
		long calcFlowCost() {
			// Calculate the cost of the flow
			long cost = 0;
			for (Node n : nodes) {
				for (Edge e : n.edges) {
					if (e.flow > 0) {
						cost += e.cost * e.flow;
					}
				}
			}
			return cost;
		}
	}

	/**
	 * Dinic's algorithm, Shimon Even variant.
	 */
	static class Dinic extends MaxFlowSolver
	{
	    int [] dist;          // distance from src for level graph
	    boolean [] blocked;   // true if all outgoing edges blocked in residual graph

	    int BlockingFlow(Node src, Node snk) {
	        int N = nodes.size();
	        dist = new int[N];
	        Arrays.fill(dist, -1);
	        int [] Q = new int[N];
	        int s = src.index;
	        int t = snk.index;
	  
	        /* Step 1.  BFS from source to compute levels */
	        dist[s] = 0;
	        int head = 0, tail = 0;
	        Q[tail++] = s;
	        while (head < tail) {
	            int x = Q[head++];
	            List<Edge> succ = nodes.get(x).edges;
	            for (Edge e : succ) {
	                if (dist[e.to.index] == -1 && e.remaining() > 0) {
	                    dist[e.to.index] = dist[e.from.index] + 1;
	                    Q[tail++] = e.to.index;
	                }
	            }
	        }

	        if (dist[t] == -1)     // no flow if sink is not reachable
	            return 0;

	        /* Step 2. Push flow down until we have a blocking flow */
	        int flow, totflow = 0;
	        blocked = new boolean[N];
	        do {
	            flow = dfs(src, snk, Integer.MAX_VALUE);
	            totflow += flow;
	        } while (flow > 0);
	        return totflow;
	    }

	    /*
	     * Run DFS on the BFS level graph.
	     */
	    int dfs(Node v, Node snk, int mincap) {
	        // reached sink
	        if (v == snk)
	            return mincap;

	        for (Edge e : v.edges) {
	            // standard DFS, but consider an edge only if
	            if (!blocked[e.to.index]    // the path to the sink is not already blocked
	                && dist[e.from.index] + 1 == dist[e.to.index] // it's in the BFS level graph
	                && e.remaining() > 0) {  // the edge has remaining capacity
	                int flow = dfs(e.to, snk, min(mincap, e.remaining()));
	                if (flow > 0) {
	                    e.addFlow(flow);
	                    return flow;
	                }
	            }
	        }
	        // if we couldn't add any flow then there is no point in ever going
	        // past this node again.  Mark it blocked.
	        blocked[v.index] = true;
	        return 0;
	    }

	    @Override
	    int getMaxFlow(Node src, Node snk) {
	        int flow, totflow = 0;
	        while ((flow = BlockingFlow(src, snk)) != 0)
	            totflow += flow;
	        return totflow;
	    }

	    Dinic () { this(0); }
	    Dinic (int n) { super(n); }
	}
}