dijkstra

#include <bits/stdc++.h>
#define newline '\n'
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
///***********************
const int NMAX = 5e4 + 5;
const int OO = (1 << 30);
int dis[NMAX];
bool vis[NMAX];
class item
{
public:
    int node;
    int dis;
    bool operator < (const item &other) const noexcept
    {
        return this->dis > other.dis;
    }
};
array<vector<item>, NMAX> graph;
priority_queue<item> q;
int n, m;

void read()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b, c;
        fin >> a >> b >> c;
        graph[a].push_back({b, c});
    }
}

void dijkstra(int start)
{
    item e;
    fill(dis, dis + NMAX, OO);
    dis[start] = 0;
    q.push({1, 0});
    while (!q.empty())
    {
        e = q.top();
        q.pop();
        if (vis[e.node])
            continue;
        vis[e.node] = true;
        for (auto nei : graph[e.node])
        {
            if (dis[nei.node] > nei.dis + dis[e.node])
            {
                dis[nei.node] = nei.dis + dis[e.node];
                nei.dis = dis[nei.node];
                q.push(nei);
            }
        }
    }
}

void display()
{
    for (int i = 2; i <= n; i++)
        if (dis[i] == OO)
            fout << 0 << ' ';
        else
            fout << dis[i] << ' ';
}

int main()
{
    read();
    dijkstra(1);
    display();
    fout.close();
    return 0;
}