== include(page="template/taskheader" task_id="harta3") ==

Consideram $N$ puncte pe axa $OX$ avand coordonate intregi. Se dau $M$ relatii de forma $X Y D$ semnificand faptul ca $X$ se afla la stanga lui $Y$ cu $D$ unitati. Se mai dau punctele speciale $A$ si $B$, care fac parte din cele $N$.

Considerăm $N$ puncte pe axa $OX$ având coordonate întregi. Se dau $M$ relaţii de forma $X Y D$ semnificând faptul că $X$ se află la stânga lui $Y$ cu $D$ unitaţi. Se mai dau punctele speciale $A$ şi $B$, care fac parte din cele $N$.

h2. Cerinta

h2. Cerinţa

Atribuiti coordonate **diferite** celor $N$ puncte astfel incat sa se respecte cele $M$ relatii, iar distanta intre $A$ si $B$ sa fie cat mai mica.

Atribuiţi coordonate **diferite** celor $N$ puncte astfel încat să se respecte cele $M$ relaţii, iar distanţa între $A$ şi $B$ să fie cât mai mică.

h2. Date de intrare

Fisierul de intrare $harta3.in$ contine pe prima linie numerele $N$ si $M$, cu semnificatia din enunt. Pe a doua linie se afla punctele $A$ si $B$. Urmatoarele $M$ linii contin cate $3$ numere $X, Y$ si $D$.

Fişierul de intrare $harta3.in$ conţine pe prima linie numerele $N$ şi $M$, cu semnificaţia din enunţ. Pe a doua linie se află punctele $A$ şi $B$. Urmatoarele $M$ linii conţin câte $3$ numere $X, Y$ şi $D$.

h2. Date de iesire

Fisierul de iesire $harta3.out$ contine pe prima linie $N$ numere reprezentand coordonatele pe axa $OX$ a celor $N$ puncte.

Fişierul de ieşire $harta3.out$ conţine pe prima linie $N$ numere reprezentând coordonatele pe axa $OX$ a celor $N$ puncte.

h2. Restrictii si precizari

h2. Restricţii şi precizari

* $2 ≤ N ≤ 10.000$
* $0 ≤ M ≤ 10.000$
* Pentru fiecare $X, Y, D, 1 &le; X < Y &le; N$ si $1 &le; D &le; 1.000$.
* **Atentie!** Se garanteaza ca distanta minima intre $A$ si $B$ &le; $200$.
* Coordonatele punctelor trebuie sa apartina intervalului $[-1.000.000, 1.000.000]$.
* In cazul in care exista mai multe solutii, se poate afisa oricare dintre acestea.
* **Se garanteaza ca exista solutie!**

* $2 ≤ N ≤ 10 000$
* $0 ≤ M ≤ 10 000$
* Pentru fiecare $X, Y, D, 1 ≤ D ≤ 100$.
* **Atenţie!** Se garantează că distanţa minimă între $A$ şi $B$ ≤ $2 400$.
* Coordonatele punctelor trebuie să aparţina intervalului $[-1 000 000, 1 000 000]$.
* În cazul în care exista mai multe soluţii, se poate afişa oricare dintre acestea.
* **Se garanteaza ca exista soluţie!**

h2. Exemplu

4647