#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define Nmax 50001

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n, m, dist[Nmax], viz[Nmax];
vector <pair<int, int> > gr[Nmax];
priority_queue <pair<int ,int>, vector<pair<int, int> >, greater<pair<int,int> > > c;
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        f>>x>>y>>z;
        gr[x].push_back(make_pair(y, z));
    }
    for(int i=1;i<=n;i++)
        dist[i]=1000000;
    c.push(make_pair(0, 1));
    viz[1]=1;
    dist[1]=0;
    while(!c.empty())
    {
        pair<int, int> fr=c.top();
        c.pop();
        for(auto i:gr[fr.second])
        {
            if(dist[i.first]>dist[fr.second]+i.second)
            {
                dist[i.first]=dist[fr.second]+i.second;
                if(viz[i.first]==0)
                {
                    viz[i.first]=1;
                    c.push(make_pair(dist[i.first], i.first));
                }
            }
        }
    }
    for(int i=2;i<=n;i++)
        g<<dist[i]<<" ";
    return 0;
}