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

#define NMax 50005

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

int n,m;

struct muchie
{
    int y,c;

    bool operator< (const muchie &t) const
    {
        return (c>t.c);
    }

    bool operator> (const muchie &t) const
    {
        return (c<t.c);
    }

    bool operator== (const muchie &t) const
    {
        return (c==t.c);
    }
}u;

priority_queue< muchie,vector<muchie> > cd;

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

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

void djk(int s)
{
    muchie q;

    D[s]=1;
    add(s);

    while(!cd.empty())
    {
        q=cd.top();
        cd.pop();

        if(D[q.y]==0)
        {
            D[q.y]=q.c;
            add(q.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<<D[i]-1<<" ";

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