#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;
struct vertex{
 int nod,cost;
 vertex* next;
};
bool comp( const pair<int,int>&x, const pair<int,int>&y ){
if(x.second>y.second)
    return true;
return false;
}

void dij(){
make_heap( minHeap.begin(), minHeap.end(), comp );

int i,j,tempDist;
/*for( i = 0; i < minHeap.size(); i ++ )
        cout<<minHeap[i].first+1<<"("<<minHeap[i].second<<") ";
    cout<<"\n\n";*/
pair<int,int> curr;
while(!minHeap.empty())
    {
    curr = minHeap.front();
    //cout<<curr.first+1<<":\n";
    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;
                //cout<<minHeap[j].first+1<<"~tempDist: "<<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
                    }

                //cout<<minHeap[j].first+1<<"("<<minHeap[j].second<<")\n";
                break;
                }
            }
        }
    dist[curr.first] = curr.second;
    pop_heap( minHeap.begin(), minHeap.end(), comp );
    minHeap.pop_back();
    make_heap( minHeap.begin(), minHeap.end(), comp );
    /*for( i = 0; i < minHeap.size(); i ++ )
        cout<<minHeap[i].first+1<<"("<<minHeap[i].second<<") ";
    cout<<"\n\n";*/
    }
}

int main()
{
int x, y, z, i;
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) );
    }
dij();


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