Restore the Recipe

All submissions for this problem are available.
Chef has had a recipe. He had written it as a sequence of N integer numbers A[1], A[2], ..., A[N]. To be on the safe side, he decided to write out M triples of numbers, where ith triple is composed of three numbers X_{i}, Y_{i} and Z_{i}. It means that the sum of numbers in the recipe from X_{i}th to Y_{i}th is equal to Z_{i}. In other words, A[X_{i}] + A[X_{i} + 1] + ... + A[Y_{i}] = Z_{i}. Unfortunately, the recipe has been recently lost. So Chef needs to restore his recipe using these M triples. Your task is to help him.
Input
The first line contains two space separated integer numbers N and M.
Then M lines follow. Each line contains three space separated integer numbers X_{i}, Y_{i} and Z_{i}. It means that the sum of numbers in the recipe from X_{i}th to Y_{i}th is equal to Z_{i}.
Output
If there is a solution output N space separated integer numbers  the sequence that you have restored. If there are several solutions you can output any of them. However, any number in the output should be no more than 10^{14} by its absolute value. If it is impossible to restore the sequence output "1" without quotes.
Constraints
 2 ≤ N ≤ 65536
 1 ≤ M ≤ 200000
 1 ≤ X_{i} ≤ Y_{i} ≤ N
 Z_{i} ≤ 1000000000 (10^{9})
 If It is possible to restore the sequence then there is way to do this such that every number in the restored sequence is in range [10000; 10000]
Example
Input 1: 4 4 1 2 3 2 3 1 3 4 2 1 4 1 Output 1: 1 2 1 1 Input 2: 5 3 1 3 4 4 5 6 1 5 9 Output 2: 1
Explanation
In the first test case the answer is not unique. Possible answers are also {0, 3, 2, 0}, {2, 1, 0, 2} and many others.
In the second test case first two conditions imply A[1] + A[2] + A[3] = 4 and A[4] + A[5] = 6 and hence A[1] + A[2] + A[3] + A[4] + A[5] = (A[1] + A[2] + A[3]) + (A[4] + A[5]) = 4 + 6 = 10. And it contradicts to the third condition. Hence it is impossible to restore the recipe.
Author:  xcwgf666 
Tester:  anton_lunyov 
Editorial  http://discuss.codechef.com/problems/RSRECIPE 
Tags  feb12, medium, xcwgf666 
Date Added:  12112011 
Time Limit:  0.298851 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions