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 fmax A set of flows {f1, f2, ..., fn} 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 ai belongs to R.

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

Given graph G find its maximal flows dimension.

Input

The first line 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 104. It is guaranteed that there is a path from source to sink.

Output

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