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 java.io.*;
import java.util.*;


public class DeliveryBears {
	static int N, M, X;
	static List<E>[] graph;
	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		N = sc.nextInt();
		M = sc.nextInt();
		X = sc.nextInt();
		graph = new ArrayList[N];
		for (int n = 0; n < N; n++)	{
			graph[n] = new ArrayList<E>();
		}
		for (int m = 0; m < M; m++)	{
			graph[sc.nextInt()-1].add(new E(sc.nextInt()-1, sc.nextDouble()));
		}
		double max = findMax();
		double ans = binarySearch(max);
		System.out.println(ans);
	}
	public static boolean works(double weight)	{
		double target = weight * X;
		MaxFlowSolver mf = new Dinic();
		Node source = mf.addNode();
		Node sink = mf.addNode();
		Node[] nodes = new Node[N];
		for (int n = 0; n < N; n++)	{
			nodes[n] = mf.addNode();
		}
		mf.link(source, nodes[0], Long.MAX_VALUE);
		mf.link(nodes[N-1], sink, Long.MAX_VALUE);
		for (int n = 0; n < N; n++)	{
			for (E e : graph[n])	{
				mf.link(nodes[n], nodes[e.to], Math.max(0, ((e.weight - (e.weight % weight)))));
			}
		}
		return mf.getMaxFlow(source, sink) >= target - 1E-9;
		
		
	}
	public static double binarySearch(double max)	{
		double min = 0;
		double mid = -1;
		for (int i = 0; i < 60; i++)	{
			mid = (max + min )/ 2.0;
			if (works(mid))	{
				min = mid;
			} else {
				max = mid;
			}
		}
		return mid*X;
	}
	public static double findMax()	{
		MaxFlowSolver mf = new Dinic();
		Node source = mf.addNode();
		Node sink = mf.addNode();
		Node[] nodes = new Node[N];
		for (int n = 0; n < N; n++)	{
			nodes[n] = mf.addNode();
		}
		mf.link(source, nodes[0], Long.MAX_VALUE);
		mf.link(nodes[N-1], sink, Long.MAX_VALUE);
		for (int n = 0; n < N; n++)	{
			for (E e : graph[n])	{
				mf.link(nodes[n], nodes[e.to], e.weight);
			}
		}
		return mf.getMaxFlow(source, sink);
	}
	
	
	
	
	public static class E {
		int to;
		double weight;
		public E(int to, double weight)	{
			this.to= to;
			this.weight = weight;
		}
	}

	
	
	public 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

	    int dist;
	    boolean active;
	    boolean blocked;
	}

	public static class Edge
	{
	    boolean forward; // true: edge is in original graph
	    // false: edge is a backward edge
	    Node from, to;   // nodes connected
	    double flow;        // current flow
	    final double 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, double c, boolean f)
	    {
	        forward = f;
	        from = s;
	        to = d;
	        capacity = c;
	    }

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

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

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

	    /* Create an edge between nodes n1 and n2 */
	    public void link(Node n1, Node n2, double capacity)
	    {
	    /*
	     * Only the EdmondsKarp solver takes cost into account
	     * during getMaxFlow().  Setting it to 1 for problems
	     * that do not involve cost means it uses a shortest path
	     * search when finding augmenting paths.  In practice,
	     * this does not seem to make a difference.
	     */
	        link(n1, n2, capacity, 1);
	    }

	    /* Create an edge between nodes n1 and n2 and assign cost */
	    public void link(Node n1, Node n2, double 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, double 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); }

	    public abstract double getMaxFlow(Node src, Node snk);

	    /* Add a new node. */
	    public 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;
	    }
	}

	/**
	 * Dinic's algorithm, Shimon Even variant.
	 */
	public static class Dinic extends MaxFlowSolver
	{
	    double BlockingFlow(Node src, Node snk) {
	        int N = nodes.size();
	        for (Node u : nodes) {
	            u.dist = -1;
	            u.blocked = false;
	        }
	        Node [] Q = new Node[N];

	        /* Step 1.  BFS from source to compute levels */
	        src.dist = 0;
	        int head = 0, tail = 0;
	        Q[tail++] = src;
	        while (head < tail) {
	            Node x = Q[head++];
	            List<Edge> succ = x.edges;
	            for (Edge e : succ) {
	                if (e.to.dist == -1 && e.remaining() > 0) {
	                    e.to.dist = e.from.dist + 1;
	                    Q[tail++] = e.to;
	                }
	            }
	        }

	        if (snk.dist == -1)     // no flow if sink is not reachable
	            return 0;

	        double flow;
			/* Step 2. Push flow down until we have a blocking flow */
	        double totflow = 0;
	        do {
	            flow = dfs(src, snk, Long.MAX_VALUE);
	            totflow += flow;
	        } while (flow > 0);
	        return totflow;
	    }

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

	        for (Edge e : v.edges) {
	            // standard DFS, but consider an edge only if
	            if (!e.to.blocked    // the path to the sink is not already blocked
	                    && e.from.dist + 1 == e.to.dist // it's in the BFS level graph
	                    && e.remaining() > 0) {  // the edge has remaining capacity
	                double flow = dfs(e.to, snk, Math.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.
	        v.blocked = true;
	        return 0;
	    }

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

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

	/**
	 * Implements Edmonds/Karp min-cost max-flow.
	 *
	 * This algorithm uses costs to find an mincost augmenting path.
	 *
	 * See Theoretical Improvements in Algorithmic Efficiency for
	 * Network Flow Problems by Edmonds and Karp,
	 * Journal of the Association for Computing Machinery,
	 * Vol. 19, No. 2, Apri; 1972. pp. 248-264.
	 */
	
	
	public static class FastScanner {
		BufferedReader br;
		StringTokenizer st;

		public FastScanner(Reader in) {
			br = new BufferedReader(in);
		}

		public FastScanner() {
			this(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		String readNextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}

		int[] readIntArray(int n) {
			int[] a = new int[n];
			for (int idx = 0; idx < n; idx++) {
				a[idx] = nextInt();
			}
			return a;
		}

		long[] readLongArray(int n) {
			long[] a = new long[n];
			for (int idx = 0; idx < n; idx++) {
				a[idx] = nextLong();
			}
			return a;
		}
	}
}