#include <fstream>
#include <vector>
#include <queue>
using namespace std;

#define NMax 50001

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

struct muchie{int x,y,t;};

class Compare {
public:
    bool operator()(muchie& t1,muchie& t2)
    {
        if(t1.t>t2.t) return true;
        return false;
    }
};

vector<int> v[NMax],w[NMax];
priority_queue<muchie, vector<muchie>,Compare> cd;
int n,m;
int dr[NMax],viz[NMax];

void add(int s)
{
    int i,e;
    muchie u;
    e=v[s].size();
    for(i=0;i<e;i++)
    {
        if(viz[v[s].at(i)]==0)
        {
            u.x=s;
            u.y=v[s].at(i);
            u.t=dr[s]+w[s].at(i);
            cd.push(u);
        }
    }
}

void djk(int s)
{
    muchie u;
    viz[s]=1;
    add(s);
    while(!cd.empty())
    {
        u=cd.top();
        cd.pop();
        if(viz[u.y]==0)
        {
            viz[u.y]=1;
            dr[u.y]=u.t;
            add(u.y);
        }
    }
}

int main()
{
    int i,a,b,c;

    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>a>>b>>c;
        v[a].push_back(b);
        w[a].push_back(c);
    }

    djk(1);

    for(i=2;i<=n;i++) g<<dr[i]<<" "; g<<"\n";

    f.close();
    g.close();
    return 0;
}