#include<fstream>
#include<cstring>
#define nmax 250000
#define inf -1
#include <vector>
using namespace std;

vector <int> a[nmax];
vector <int> b[nmax];

int v[nmax],n;


void dij()
{
    int i;
    v[1]=0;
    vector<int>::iterator ita,itb;
    for(i=1;i<=n;i++)
    {
        for(ita=a[i].begin(),itb=b[i].begin();ita!=a[i].end();ita++,itb++)
        {
            if(v[*ita]>v[i]+*itb || v[*ita]==-1)
                v[*ita]=v[i]+*itb;
        }
    }
}


void citire()
{
    ifstream in("dijkstra.in");
    int i,x,y,val,m;
    in>>n>>m;
    for(i=1;i<=n;i++)
    v[i]=-1;
    for(i=1;i<=m;i++)
        {
            in>>x>>y>>val;
            a[x].push_back(y);
            b[x].push_back(val);
            a[y].push_back(x);
            b[y].push_back(val);
        }
    in.close();
}

void afisare()
{
    int i;
    ofstream out("dijkstra.out");
    for(i=2;i<=n;i++)
        out<<v[i]<<' ';
    out.close();
}
int main()
{
    int m;
    citire();
    dij();
    afisare();

}