#include <fstream>
#include <queue>
#include <vector>

using namespace std;

ifstream fin( "dijkstra.in" );
ofstream fout( "dijkstra.out" );

const int INF = ( 1 << 30 );
const int NMAX = 50005;

int N, M;

typedef pair < int, int > Pair;

int d[NMAX];

vector <int> Ad[NMAX];
vector <int> Cost[NMAX];

bool vis[NMAX];

void Read()
{
fin >> N >> M;

int a, b, d;

while( fin >> a >> b >> d )
{
++M;

Ad[a].push_back(b);
Cost[a].push_back(d);
}

fin.close();
}

void Do()
{
for( int i = 1; i <= N; ++i )
d[i] = INF;

d[1] = 0;

priority_queue < Pair, vector<Pair>, greater<Pair> > H;

H.push( make_pair( 0, 1) );

int nod, w;

while( !H.empty() )
{
nod = H.top().second;
H.pop();

if( vis[nod] ) continue;
else vis[nod] = true;

for( int i = 0; i < Ad[nod].size(); ++i )
{
w = Ad[nod][i];

if( d[w] > d[nod] + Cost[nod][i] )
{
d[w] = d[nod] + Cost[nod][i];

H.push( make_pair( d[w], w ) );
}
}
}
}

void Print()
{
for( int i = 2; i <= N; ++i )
if( d[i] == INF ) fout << "0 ";
else fout << d[i] << ' ';

fout.close();
}

int main()
{
Read();
Do();
Print();

return 0;
}