Mail Carrier

A small village has N houses and M roads. Each road connects two houses, and each road has one mailbox on it.

The mail carrier wants to collect the mail by traveling along every road exactly once. The village is guaranteed to have at least one such route.

The mailbox on the i-th road has weight w[i]. If that road is traversed as the k-th road of the route, the carrier gains w[i]-k when k is smaller than w[i], and loses k-w[i] when k is larger than w[i]. Total profit is the gain minus the loss.

Print a route that traverses every road exactly once and maximizes the total profit.

The first line contains N(1 <= N <= 1,000) and M(1 <= M <= 100,000). Each of the next M lines contains a[i], b[i], and w[i] for the i-th road. This means that the i-th road connects house a[i] and house b[i].

It is guaranteed that a[i] != b[i], and w[i] is a positive integer with at most 8 digits.

Print the house numbers in visiting order, one per line. Print -1 on the last line.