#include <iostream>
#include <climits>
using namespace std;
int findminvertex(int *distance, bool *visited, int n)
{
int minvertex = -1;
for (int i = 0; i < n; i++)
{
if (!visited[i] && (minvertex == -1 || distance[i] < distance[minvertex]))
{
minvertex = i;
}
}
return minvertex;
}
void dijistra(int **edges, int n)
{
int *distance = new int[n];
bool *visited = new bool[n];
for (int i = 0; i < n; i++){
distance[i] = INT_MAX;
visited[i] = false;
}
distance[0] = 0;
for (int i = 0; i < n - 1; i++){
int minvertex = findminvertex(distance, visited, n);
for (int j = 0; j < n; j++){
if (edges[minvertex][j] != 0 && !visited[j])
{
int dist = distance[minvertex] + edges[minvertex][j];
if (dist < distance[j])
{
distance[j] = dist;
}
}
}
for (int i = 0; i < n; i++)
{
cout << i << " " << distance[i] << endl;
}
// delete[] visited;
// delete[] distance;
}
}
int main(){
int n;
int e;
cin >> n >> e;
int **edges = new int *[n];
for (int i = 0; i < e; i++)
{
edges[i] = new int[n];
for (int j = 0; j < n; j++)
{
edges[i][j] = 0;
}
}
for (int i = 0; i < e; i++)
{
int f, s, weight;
cin >> f >> s >> weight;
edges[f][s] = weight;
edges[s][f] = weight;
}
cout << endl;
dijistra(edges, n);
for (int i = 0; i < e; i++)
{
delete[] edges[i];
}
delete[] edges;
}
CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPGNsaW1pdHM+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IGZpbmRtaW52ZXJ0ZXgoaW50ICpkaXN0YW5jZSwgYm9vbCAqdmlzaXRlZCwgaW50IG4pCnsKICAgICAgaW50IG1pbnZlcnRleCA9IC0xOwogICAgICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykKICAgICAgewogICAgICAgICAgICBpZiAoIXZpc2l0ZWRbaV0gJiYgKG1pbnZlcnRleCA9PSAtMSB8fCBkaXN0YW5jZVtpXSA8IGRpc3RhbmNlW21pbnZlcnRleF0pKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgIG1pbnZlcnRleCA9IGk7CiAgICAgICAgICAgIH0KICAgICAgfQogICAgICByZXR1cm4gbWludmVydGV4Owp9Cgp2b2lkIGRpamlzdHJhKGludCAqKmVkZ2VzLCBpbnQgbikKewogICAgICBpbnQgKmRpc3RhbmNlID0gbmV3IGludFtuXTsKICAgICAgYm9vbCAqdmlzaXRlZCA9IG5ldyBib29sW25dOwogICAgICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKyl7CiAgICAgICAgICAgIGRpc3RhbmNlW2ldID0gSU5UX01BWDsKICAgICAgICAgICAgdmlzaXRlZFtpXSA9IGZhbHNlOwogICAgICB9CgogICAgICBkaXN0YW5jZVswXSA9IDA7CiAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbiAtIDE7IGkrKyl7CiAgICAgICAgICAgIGludCBtaW52ZXJ0ZXggPSBmaW5kbWludmVydGV4KGRpc3RhbmNlLCB2aXNpdGVkLCBuKTsKICAgICAgICAgICAgZm9yIChpbnQgaiA9IDA7IGogPCBuOyBqKyspewogICAgICAgICAgICAgICAgICBpZiAoZWRnZXNbbWludmVydGV4XVtqXSAhPSAwICYmICF2aXNpdGVkW2pdKQogICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIGludCBkaXN0ID0gZGlzdGFuY2VbbWludmVydGV4XSArIGVkZ2VzW21pbnZlcnRleF1bal07CiAgICAgICAgICAgICAgICAgICAgICAgIGlmIChkaXN0IDwgZGlzdGFuY2Vbal0pCiAgICAgICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZGlzdGFuY2Vbal0gPSBkaXN0OwogICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICBjb3V0IDw8IGkgPDwgIiAiIDw8IGRpc3RhbmNlW2ldIDw8IGVuZGw7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgLy8gZGVsZXRlW10gdmlzaXRlZDsKICAgICAgICAgICAgLy8gZGVsZXRlW10gZGlzdGFuY2U7CiAgICAgIH0KfQoKaW50IG1haW4oKXsKICAgICAgaW50IG47CiAgICAgIGludCBlOwogICAgICBjaW4gPj4gbiA+PiBlOwogICAgICBpbnQgKiplZGdlcyA9IG5ldyBpbnQgKltuXTsKICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBlOyBpKyspCiAgICAgIHsKICAgICAgICAgICAgZWRnZXNbaV0gPSBuZXcgaW50W25dOwogICAgICAgICAgICBmb3IgKGludCBqID0gMDsgaiA8IG47IGorKykKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICBlZGdlc1tpXVtqXSA9IDA7CiAgICAgICAgICAgIH0KICAgICAgfQoKICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBlOyBpKyspCiAgICAgIHsKICAgICAgICAgICAgaW50IGYsIHMsIHdlaWdodDsKICAgICAgICAgICAgY2luID4+IGYgPj4gcyA+PiB3ZWlnaHQ7CiAgICAgICAgICAgIGVkZ2VzW2ZdW3NdID0gd2VpZ2h0OwogICAgICAgICAgICBlZGdlc1tzXVtmXSA9IHdlaWdodDsKICAgICAgfQogICAgICBjb3V0IDw8IGVuZGw7CiAgICAgIGRpamlzdHJhKGVkZ2VzLCBuKTsKICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBlOyBpKyspCiAgICAgIHsKICAgICAgICAgICAgZGVsZXRlW10gZWRnZXNbaV07CiAgICAgIH0KICAgICAgZGVsZXRlW10gZWRnZXM7Cn0K