#include <fstream>
#include <vector>
#include <queue>
#define in "dijkstra.in"
#define out "dijkstra.out"
#define oo 1e7
#define N 50003

using namespace std;

ifstream fin(in);
ofstream fout(out);

int n,m,x,y,c;
vector<pair<int,int> > g[N]; // v[x][y] = c, g[x].(y,c)

priority_queue<pair<int,int> >q; // q.first = -dist, q.second = nod_urm

int d[N];

void Dijkstra()
{
    for(int i=2; i<=n; ++i)
        d[i] = oo;

    q.push(make_pair(0,1));

    int cost,nod,nodurm,costurm;

    while(!q.empty())
    {
        cost = -q.top().first;
        nod = q.top().second;

        for(int i=0; i<g[nod].size(); ++i)
        {
            nodurm = g[nod][i].first;
            costurm = g[nod][i].second;

            if(d[nodurm] > cost + costurm)
            {
                d[nodurm] = cost + costurm;
                q.push(make_pair(-d[nodurm],nodurm));
            }
        }
        q.pop();
    }
}

int main()
{
    fin>>n>>m;
    while(m--)
    {
        fin>>x>>y>>c;
        g[x].push_back(make_pair(y,c));
    }

    Dijkstra();

    for(int i=2; i<=n; ++i)
        fout<<d[i]<<" ";

    fin.close(); fout.close();
    return 0;
}