{\rtf1\ansi\deff0\nouicompat{\fonttbl{\f0\fnil\fcharset0 Calibri;}}
{\*\generator Riched20 10.0.10586}\viewkind4\uc1 
\pard\sa200\sl276\slmult1\f0\fs22\lang9 #include <fstream>\par
#include <vector>\par
#include <algorithm>\par
#include <queue>\par
using namespace std;\par
 \par
#define FILEIN "dijkstra.in"\par
#define FILEOUT "dijkstra.out"\par
 \par
const int MAXN = 50005;\par
const int INF = 0x3f3f3f3f;\par
 \par
int N, M;\par
vector< pair<int, int> > G[MAXN];\par
int Dmin[MAXN];\par
 \par
void ReadData() \{\par
    ifstream fin(FILEIN);\par
 \par
    fin >> N >> M;\par
    for (int i = 0; i < M; ++i) \{\par
        int a, b, c;\par
 \par
        fin >> a >> b >> c;\par
        G[a].push_back(make_pair(b, c));\par
    \}\par
\}\par
 \par
void Solve() \{\par
    bool InQueue[MAXN];\par
    queue<int> Q;\par
 \par
    memset(Dmin, INF, sizeof(Dmin));\par
    memset(InQueue, false, sizeof(InQueue));\par
 \par
    Dmin[1] = 0;\par
    Q.push(1);\par
    InQueue[1] = true;\par
 \par
    while (!Q.empty()) \{\par
        int nod = Q.front();\par
        Q.pop();\par
        InQueue[nod] = false;\par
 \par
        for (vector< pair<int, int> >::iterator it = G[nod].begin(); it != G[nod].end(); ++it)\par
if (!InQueue[it->first]) \{            \par
if (Dmin[nod] + it->second < Dmin[it->first]) \{\par
                Dmin[it->first] = Dmin[nod] + it->second;\par
                    Q.push(it->first);\par
                    InQueue[it->first] = true;\par
                \}\par
            \}\par
    \}\par
\}\par
 \par
void WriteData() \{\par
    ofstream fout(FILEOUT);\par
 \par
    for (int i = 2; i <= N; ++i)\par
        fout << (Dmin[i] < INF ? Dmin[i] : 0) << " ";\par
\}\par
 \par
int main() \{\par
    ReadData();\par
    Solve();\par
    WriteData();\par
\}\par
}