#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <deque>
#include <queue>
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int MAX_NODES = 50000;
const long long MAX_DISTANCE = 5000000000;

vector<pair<int, int>> graph[MAX_NODES + 1];

priority_queue<int> currentNodes;

pair<int, int> arch;

long long minDistance[MAX_NODES + 1];

int main() {
    int noNodes, noArches;
    fin >> noNodes >> noArches;
    for (int i = 1; i <= noArches; ++i) {
        int startNode;
       // pair<int, int> arch;
        fin >> startNode >> arch.first >> arch.second;
        minDistance[i] = MAX_DISTANCE + 1;
        graph[startNode].push_back(arch);
    }
    minDistance[1] = 0;
    currentNodes.push(1);
    while (currentNodes.empty() == 0) {
        int startNode = currentNodes.top();
        currentNodes.pop();
        for (vector<pair<int, int>>::iterator it = graph[startNode].begin(); it < graph[startNode].end(); ++it) {
            if (minDistance[startNode] + it->second < minDistance[it->first]) {
                minDistance[it->first] = minDistance[startNode] + it->second;
                currentNodes.push(it->first);
            }
        }
    }
   // currentNodes.push_back(1);
   /* while (currentNodes.size() > 0) {
        for (deque<int>::iterator it = currentNodes.begin(); it < currentNodes.end(); ++it) {
            for (vector<pair<int, int>>::iterator it2 = graph[*it].begin(); it2 < graph[*it].end(); ++it2) {
                if (minDistance[*it] + it2->second < minDistance[it2->first]) {
                    minDistance[it2->first] = minDistance[*it] + it2->second;
                    nextNodes.push_back(it2->first);
                }
            }
        }
        currentNodes = nextNodes;
        nextNodes.clear();
    }*/
    
    for (int i = 2; i <= noNodes; ++i) {
        if (minDistance[i] == MAX_DISTANCE + 1) {
            minDistance[i] = 0;
        }
        fout << minDistance[i] << ' ';
    }
    return 0;
}
/*
 5 6
 1 2 1
 1 4 2
 4 3 4
 2 3 2
 4 5 3
 3 5 6
 =>
 1 3 2 5
 
 5 6
 1 4 10
 1 3 9
 1 2 8
 4 5 9
 3 5 10
 2 5 11
 =>
 8 9 10 19
 
 7 7
 1 4 10
 1 3 9
 1 2 8
 4 5 9
 3 5 10
 2 5 11
 6 7 100
 =>
 8 9 10 19 0 0
 
 3 1
 2 3 20000
 =>
 0 0
 
 4 2
 1 2 0
 1 3 0
 =>
 0 0 0
 
 4 4
 1 2 0
 1 3 2
 1 4 3
 2 4 0
 =>
 0 2 0
 
 4 4
 1 2 0
 1 3 0
 1 4 0
 2 4 0
 =>
 0 0 0
 
 5 4
 2 3 0
 3 4 0
 2 4 0
 2 5 0
 =>
 0 0 0 0
 
 5 4
 2 3 6
 3 4 5
 2 4 4
 2 5 3
 =>
 0 0 0 0
 
 4 4
 1 2 20000
 2 3 20000
 3 2 20000
 2 4 20000
 =>
 20000 40000 40000
 
 5 6
 1 5 20
 1 2 1
 2 3 2
 3 4 3
 4 5 4
 5 1 5
 =>
 1 3 6 10
 
 8 8
 1 2 1
 1 3 1
 3 4 2
 2 5 2
 4 6 3
 5 7 3
 6 8 4
 7 8 5
 =>
 1 1 3 3 6 6 10
 
 Petru Trimbitas Salutare!

 ===== Ce progrese am facut de la ultimul comentariu? =====

 --> Am reusit sa obtin 60 de puncte

 ===== Ce dificultati intampin? =====

 --> Pe cele 4 teste ramase primesc eroarea "Killed by Signal 11"

 ===== Ideea generala =====

 Stochez intr-o lista toate nodurile in care ma aflu in momentul curent, iar dupa, pornind de la acestea, voi verifica daca distanta de la nodul 1 pana la nodul curent + distanta dintre nodul curent si urmatorul nod este minima. Daca s-a gasit o distanta mai mica decat cea gasita pana cum atunci nodul următor il vom pune intr-o noua lista de noduri (o putem numi lista auxiliara ce ne va ajuta sa mutam nodurile găsite in lista cu nodurile curente).

 Se reia tot acest proces pana cand nu se mai poate forma o noua lista de noduri. Cu alte cuvinte, cat timp se mai gaseste o distanta minima dintre nodul 1 si nodul "i" se va relua tot procesul de mai sus.

 ===== Pasii de implementare =====

 1) Citesc input-ul folosindu-ma de un vector in felul urmator:

 --> pentru fiecare nod de început al muchiei dintr-un vector pe fiecare pozitie voi avea un sir de perechi in care am stocate doua valori: cealalta nodul de sfârșit al muchiei, respectiv lungimea muchiei

 2) Imi declar un sir de tip long long cu 50.000 elemente ce contine distantele minime cerute, iar fiecare pozitie va avea stocata initial distanta maxima, adica 5 * 10^9.

 3) Voi avea un "deque" ce reprezinta o lista cu nodurile in care ma aflu in fiecare moment. Pentru început, aceasta va contine doar nodul 1.

 4) Cu ajutorul unui "while" ce se va opri cand lista cu nodurile curente este goală voi face următoarele:

 4. 1) Parcurg toate nodurile din lista cu noduri curente.

 4. 2) Pentru fiecare nod de mai susverific daca distanta de la nodul 1 pana la el + distanta dintre el si nodul urmator acestuia este minima. In caz afirmativ modific distanta minima de la nodul 1 pana la nodul următor, iar acest nod il voi pune intr-o lista auxiliară (adica intr-un alt "deque").

 4. 3) Dupa ce am parcurs toate nodurile din lista curenta voi actualiza aceasta lista cu nodurile adaugate in lista auxiliară.

 5) Afisez distantele minime de la nodul 1 la fiecare dintre nodurile >= 2. Daca distanta minima de la nodul 1 la un nod "i" nu s-a modificat pe parcurs atunci aceasta va fi 0 (nu exista cale de acces intre aceste 2 noduri).

 ===== Lista cu teste =====

 5 6
  1 2 1
  1 4 2
  4 3 4
  2 3 2
  4 5 3
  3 5 6
  =>
  1 3 2 5
  
  5 6
  1 4 10
  1 3 9
  1 2 8
  4 5 9
  3 5 10
  2 5 11
  =>
  8 9 10 19
  
  7 7
  1 4 10
  1 3 9
  1 2 8
  4 5 9
  3 5 10
  2 5 11
  6 7 100
  =>
  8 9 10 19 0 0
  
  3 1
  2 3 20000
  =>
  0 0
  
  4 2
  1 2 0
  1 3 0
  =>
  0 0 0
  
  4 4
  1 2 0
  1 3 2
  1 4 3
  2 4 0
  =>
  0 2 0
  
  4 4
  1 2 0
  1 3 0
  1 4 0
  2 4 0
  =>
  0 0 0
  
  5 4
  2 3 0
  3 4 0
  2 4 0
  2 5 0
  =>
  0 0 0 0
  
  5 4
  2 3 6
  3 4 5
  2 4 4
  2 5 3
  =>
  0 0 0 0
  
  4 4
  1 2 20000
  2 3 20000
  3 2 20000
  2 4 20000
  =>
  20000 40000 40000
  
  5 6
  1 5 20
  1 2 1
  2 3 2
  3 4 3
  4 5 4
  5 1 5
  =>
  1 3 6 10
  
  8 8
  1 2 1
  1 3 1
  3 4 2
  2 5 2
  4 6 3
  5 7 3
  6 8 4
  7 8 5
  =>
  1 1 3 3 6 6 10

 ===== Dificultatea explicata =====

 Cred ca intampin acea eroare din cauza ca folosesc prea multa memorie si nu mai are unde sa fie stocata.

 M-am uitat si la indicatiile de rezolvare ale problemei si am vazut ca era o solutie cu un "heap". Am sa ma uit sa vad cum ma pot folosi de ea.

 Pana atunci, am inteles bine din ideea generala si pasii de implementare care e principiul algoritmului lui Dijkstra?
 */