#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define inf 5001
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,    d[inf], s[inf], t[inf];
vector <int> v[inf], a[inf];

queue <int> q, q1;

void citire()
{
    f>>n>>m;
    int i,j,k,c;
    for(k=1; k<=m; k++)
    {
        f>>i>>j>>c;
        v[i].push_back(j);
        a[i].push_back(c);
    }
}
void afis()
{
    for(int i=1; i<=n; i++)
        cout<<d[i]<<" ";
    cout<<endl;
}

void actualizeazaq(int nod, int y)
{
    int x=q.front();
    while(!q.empty() && d[x]>nod)
    {
        x=q.front();
        q.pop();
        q1.push(x);
    }
    q.push(y);
    while(!q1.empty())
    {
        x=q1.front();
        q1.pop();
        q.push(x);
    }
}

void dijkstra(int start)
{
    int i,j, poz, mn;
    //initializare
    for(i=0; i<v[start].size(); i++)
        if(v[start][i]!=start)
    {
        d[v[start][i]]=a[start][i];
        s[v[start][i]]=0;
        t[v[start][i]]=start;
        mn=d[v[start][i]];
        actualizeazaq(mn,v[start][i]);
    }
    for(i=1; i<=n; i++)
        if(d[i]==0)
            d[i]=inf;
    d[start]=0;
    s[start]=1;
    t[start]=0;
    for(i=1; i<n; i++)
    {
        while(!q.empty())
        {

            poz=q.front(); q.pop();
            s[poz]=1;
            for(j=0; j<v[poz].size(); j++)
               if(s[v[poz][j]]==0)
               if(d[v[poz][j]] > d[poz] + a[poz][j])
                {
                    d[v[poz][j]] = d[poz] + a[poz][j];
                    t[v[poz][j]] = poz;
                    mn=d[v[poz][j]];
                    actualizeazaq(mn,v[poz][j]);
                }
        }
    }

}

int main()
{
    citire();
    dijkstra(1);
    int i;
    for(i=2; i<=n; i++)
        g<<d[i]<<" ";
    f.close();
    g.close();
    return 0;
}