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 {
    public static void main(String[] args) {
        FastScanner sc = new FastScanner();

        int n = sc.nextInt();
        int m = sc.nextInt();
        int numBears = sc.nextInt();

        Link[] links = new Link[m];
        for (int i = 0; i < m; i++) {
            links[i] = new Link(sc.nextInt() - 1, sc.nextInt() - 1, sc.nextDouble());
        }

        double low = 0;
        double high = 1e6;
        for (int i = 0; i < 80; i++) {
            double mid = (low + high) / 2;
            if (check(n, numBears, links, mid)) {
                low = mid;
            } else {
                high = mid;
            }
        }

        System.out.println((low + high) / 2 * numBears);
    }

    static boolean check(int n, int numBears, Link[] links, double bearWeight) {
        MaxFlowSolver mf = new Dinic();
        Node[] nodes = new Node[n];
        for (int i = 0; i < n; i++) {
            nodes[i] = mf.addNode();
        }
        Node src = mf.addNode();
        mf.link(src, nodes[0], numBears);
        for (Link link : links) {
            mf.link(nodes[link.from], nodes[link.to], Math.round(Math.floor(link.capacity / bearWeight)));
        }
        long maxFlow = mf.getMaxFlow(src, nodes[n - 1]);
        return maxFlow == numBears;
    }

    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
        long flow;        // current flow
        final long 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, long c, boolean f)
        {
            forward = f;
            from = s;
            to = d;
            capacity = c;
        }

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

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

    /**
     * Dinic's algorithm, Shimon Even variant.
     */
    public static class Dinic extends MaxFlowSolver
    {
        long 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;

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

        /*
         * Run DFS on the BFS level graph.
         */
        long dfs(Node v, Node snk, long 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
                    long 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 long getMaxFlow(Node src, Node snk) {
            long flow, totflow = 0;
            while ((flow = BlockingFlow(src, snk)) != 0)
                totflow += flow;
            return totflow;
        }

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

    /* 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, long 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, long 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, long 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 long 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;
        }
    }

    static class Link {
        final int from, to;
        final double capacity;

        public Link(int from, int to, double capacity) {
            this.from = from;
            this.to = to;
            this.capacity = capacity;
        }
    }

    static void sort(int[] arr) {
        Random rng = new Random();
        int length = arr.length;
        for (int idx = 0; idx < arr.length; idx++) {
            int toSwap = idx + rng.nextInt(length-idx);
            int tmp = arr[idx];
            arr[idx] = arr[toSwap];
            arr[toSwap] = tmp;
        }
        Arrays.sort(arr);
    }

    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;
        }
    }
}