#include<bits/stdc++.h>
#define FIN "read.in"
#define pb push_back
#define inf 1e9
#define SIZE 50005

using namespace std;
/*
set: { {1,1},{2,3},... }
Multimea in matematica = un set de obiecte distincte
multime = {}
M = {1,2,3,4,5} => o multime de numere matematice
M = { {1,2},{2,3},{8,7},{9,9} } => o multime de perechi de numere 
M.insert(3)
multime = {obiect1, obiect2, obiect3, obiect4,...}
*/

vector< pair<int, int> > G[ SIZE ];
set< pair<int, int> > s;
int d[SIZE]; // Vector de distante
bool visited[SIZE]; // Pentru noduri vizitate
int n, // nr de noduri
    m, // nr de arce
    x, y, //arce
    c; //cost

void dijkstra() {
    d[ 1 ] = 0;
    //     first, second
    s.insert( {0, 1} );
    while( !s.empty() ) {

        set< pair<int, int> > :: iterator it = s.begin();
        int node = it->second; //obtinem descendentul
        s.erase( it );
        if( visited[ node ] ) continue;
        visited[ node ] = 1;

        for(int i = 0; i < G[node].size(); i++) {
            
            int c = G[node][i].first;
            int x = G[node][i].second;

            if(!visited[x] && d[node] + c < d[x]) {
                d[x] = d[node] + c;
                s.insert( {d[x], x} );
            }
        }
    }
}
//void read_data()
int main()
{
    cin>>n>>m;
    for(int i=1; i<=n; i++) d[i] = inf;
    for(int i=1; i<=m; i++)
    {
        cin>>x>>y>>c;
        G[ x ].push_back({c, y});
     //   cout<<"Arcul { "<<x<<" "<<y<<" }: ";
     //   cout<<" cost ="<<c<<endl;
    }
    dijkstra();
    for(int i=2; i<=n; i++) {
        cout<<(d[i] != inf ? d[i] : 0)<<" ";
    }
}