#include <fstream>
#include <vector>
#include <set>
#define inf 10000000000000000000
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

struct ura{
    int d, x;
};
vector<ura> v[50001];
set<ura> s;
set<ura>::iterator it, it1;
int d[50001] = {inf}, rez[50001];

int main()
{
    int n, m, a, b, c, i;
    in >> n >> m;
    for (i=1;i<=m;i++)
    {
        in >> a >> b >> c;
        ura nod;
        nod.x = b;
        nod.d = c;
        v[a].push_back(nod);
        if (a==1)
        {
            s.insert(nod);
            d[b] = c;
        }
    }
    d[1]=0;
    while(!s.empty())
    {
        it1 = s.begin();
        int nod = (*it1).x, mini = (*it1).d;
        for (i=0;i<v[nod].size();i++)
        {
            if (d[v[nod][i].x] > mini+v[nod][i].d)
            {
                ura vecin;
                vecin.d = d[v[nod][i].x];
                vecin.x = v[nod][i].x;
                it = s.find(vecin);
                if (it == s.end()){
                    vecin.d = mini + v[nod][i].d;
                    s.insert(vecin);
                    d[vecin.x] = vecin.d;
                }
                else
                {
                    s.erase(it);
                    vecin.d = mini + v[nod][i].d;
                    s.insert(vecin);
                    d[vecin.x] = vecin.d;
                }
            }
        }
        s.erase(it1);
    }
    for (i=2;i<=n;i++)
        out << d[i] << "\n";
    return 0;
}