#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin ("dijkstra.in");
ofstream fout("dijkstra.out");

const int NMax = 50005 , MMax = 250005 , oo = ( 1 << 31) - 1 ;
int n , m  ;

vector < pair < int , int > > vecini[NMax]  ;
vector <int> d ( NMax , oo ) ;
vector <bool> InCoada ( NMax , false ) ;
void citire ( )
{
    fin >> n >> m ;
    int x , y , z ;
    for ( int i = 1;  i <= m ; ++i )
    {
        fin >> x >> y >> z ;
        vecini[x].push_back( make_pair( y , z ) ) ;
    }
}

struct compar
{
    bool operator () ( int x , int y )
    {
        return ( d[x] > d[y] );
    }
};

priority_queue<int,vector<int>,compar> c ;

void Dijkstra ( int NodStart )
{
    d[NodStart] = 0 ;
    InCoada[NodStart] = 1;
    c.push(NodStart) ;
    int nod ;
    while ( c.size() )
    {
        nod = c.top();
        c.pop() ;
        InCoada[nod] = 0 ;
        int n = vecini[nod].size() ;
        for ( int i = 0 ; i < n ; ++i )
        {
            if ( d[vecini[nod][i].first] > d[nod] + vecini[nod][i].second )
            {
                d[vecini[nod][i].first] = d[nod] + vecini[nod][i].second ;
                if (!InCoada[vecini[nod][i].first])
                {
                    c.push( vecini[nod][i].first);
                    InCoada[vecini[nod][i].first] = true ;
                }
            }
        }
    }
}

void afis ()
{
    for ( int i = 2 ; i <= n ; ++i )
        if ( d[i] != oo ) fout << d[i] << " " ;
}


int main()
{
    citire() ;
    Dijkstra(1) ;
    afis() ;
    return 0;
}