#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

vector< vector< pair<int,int> > >graph;//graph[origine]=={destinatie,distanta_muchie}
vector< pair<int,int> >minHeap;//nod,distanta_pana_acolo
vector<int>dist;
int m, n;

int comp( const pair<int,int>&x, const pair<int,int>&y ){
return y.second-x.second;
}

void dij(){
make_heap( minHeap.begin(), minHeap.end(), comp );
int i,j,tempDist;
pair<int,int> curr;
while(!minHeap.empty())
    {
    curr = minHeap.front();
    for( i = 0; i < graph[curr.first].size(); i ++ )//parcurgem nodurile adiacente celui curent;
        {
        for( j = 0; j < minHeap.size(); j ++ )//parcurgem nodurile din minHeap
            {
            if( minHeap[j].first == graph[curr.first][i].first )//nodul adiacent curent este in minHeap
                {tempDist = curr.second + graph[curr.first][i].second;
                if ( tempDist < minHeap[j].second )//distanta calculata pe aceasta directie este mai mica decat
                    minHeap[j].second = tempDist;  //cea calculata anterior
                break;
                }
            }
        }
    dist[curr.first] = curr.second;
    pop_heap( minHeap.begin(), minHeap.end(), comp );
    minHeap.pop_back();
    make_heap( minHeap.begin(), minHeap.end(), comp );
    }
}

int main()
{
int x, y, z, i, j;
f >> n >> m;
graph.resize(n);
minHeap.resize(n);
for( i = 1; i < n; i ++ )
    {minHeap[i] = make_pair(i, 1 << 30);
    }
minHeap[0] = make_pair(0,0);
dist.resize(n,-1);
for( i = 0; i < m; i ++ )
    {f >> x >> y >> z;
    x --;
    y --;
    graph[x].push_back( make_pair(y,z) );
    graph[y].push_back( make_pair(x,z) );
    }
dij();


for( i = 1; i < n; i ++ )
    g<<dist[i]<<" ";
f.close();
g.close();
return 0;
}