Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Consider an acyclic directed graph G each edge uv of which has some associated capacity c(uv). Let G

have two special vertices: source s and sink t.

A flow in G is the function f : E → R such that the following conditions are satisfied:

1. 0 ≤ f (uv) ≤ c(uv) for all edges uv.

2. for any vertex u except s and t

The value of the flow f denoted as |f | is the amount of flow coming out of the source:

The flow is called maximal if |f | is maximal possible among all flows in G. Clearly there can be several maximal flows.

Flows can be added pointwise or multiplied by a real constant as any other functions. Let us fix some maximal flow f_{max} A set of flows {f_{1},f_{2},..., f_{n}} is said to form a basis of maximal flows if each maximal flow can be represented as the sum and no its proper subset has this property. Here α_{i} ∈ R.

The size of this set — n — is called the maximal flows dimension of the graph.

Given graph G find its maximal flows dimension.

have two special vertices: source s and sink t.

A flow in G is the function f : E → R such that the following conditions are satisfied:

1. 0 ≤ f (uv) ≤ c(uv) for all edges uv.

2. for any vertex u except s and t

The value of the flow f denoted as |f | is the amount of flow coming out of the source:

The flow is called maximal if |f | is maximal possible among all flows in G. Clearly there can be several maximal flows.

Flows can be added pointwise or multiplied by a real constant as any other functions. Let us fix some maximal flow f

The size of this set — n — is called the maximal flows dimension of the graph.

Given graph G find its maximal flows dimension.

The first line of the input file contains n and m — the number of vertices and edges in the graph, respectively (1 ≤ n ≤ 10, 1 ≤ m ≤ 10). The following m lines contain three integer numbers each and describe edges. Each edge is described by the vertex it leaves, the vertex it enters, and its capacity. The given graph is acyclic. The source has number 1, the sink has number n. Capacities do not exceed 10^{4}.

It is guaranteed that there is a path from source to sink.

It is guaranteed that there is a path from source to sink.

Output one number — the maximal flows dimension of the given graph.

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

0 1

单组数据

Please distinguish **the maximal flows dimension **and** the number of vertices, **although both of two variable are instead of **n, **they are not the same.

Andrew Stankevich Contest 22