There are two integers, separated by a single space, in the first line of the standard input: n and m (1<=N<=100000,1<=M<=1000000), denoting the number of intersections and the number of streets in Byteburg, respectively. The intersections are numbered from 1 to n. The following m lines specify successive streets, one per line. Each of those lines holds four integers separated by single spaces: a,b, s and t(1<=a<b<=N, s,t属于集合[0,1]). Such a quadruple specifies that the intersections a and b are connected with a street,

You may assume that if there exists a set of routes to carry out Byteasar's plan, then there is one in which the total number of streets that the garbage truck follows does not exceed 5*M.

In tests worth 60% of the points it additionally holds that m<=10000.

Input

第一行n，m (路口个数，街道个数)

下面m行，每行四个数x,y,z,w

x，y表示该街道连接的路口的编号，z表示初始时该街道的状态，w表示终止时该街道的状态(1=脏 0=不脏)

1<=n<=100000 1<=m<=1000000