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

#define NMax 50005

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

struct muchie
{
    int y,d;

    bool operator < (const muchie &t) const
    {
        if(t.d < d) return true;
        return false;
    }
};

priority_queue<muchie> cd;

vector<int> v[NMax],w[NMax];

int n,m;
int d[NMax];
bool viz[NMax];

void add(int s)
{
    muchie u;
    for(int i=0;i<v[s].size();++i) if(!d[v[s][i]])
    {
        u.d = d[s] + w[s][i];
        u.y = v[s][i];
        cd.push(u);
    }
}

void djk()
{
    muchie s;

    d[1] = 1;

    add(1);
    while(!cd.empty())
    {
        s = cd.top(); cd.pop();
        if(d[s.y]) continue;

        d[s.y] = s.d;
        add(s.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);
        v[b].push_back(a);
        w[a].push_back(c);
        w[b].push_back(c);
    }

    djk();

    for(i=2;i<=n;++i) g<<d[i]-1<<" "; g<<"\n";

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