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

using namespace std;

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

int n, m, p, x, y, c, d[100001], f[100001];
vector < pair <int, int> > g[100001];


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

}
};

priority_queue <int, vector <int>, compara> q;


void dijkstra(int s)
{unsigned int i, k, vecin, cost;
for(i=1; i<=n; i++)
    d[i]=1000000, f[i]=0;
d[s]=0;
f[s]=1;
q.push(s);

while(!q.empty())
{k=q.top();
q.pop();
f[k]=0;
for(i=0; i<g[k].size(); i++)
{vecin=g[k][i].first;
cost=g[k][i].second;
if(d[vecin]>d[k]+cost)
{
d[vecin]=d[k]+cost;
if(f[vecin]==0)
{f[vecin]=1;
q.push(vecin);
}

}
}

}


}


int main()
{
int i;
fin>>n>>m;
for(i=1; i<=m; i++)
{fin>>x>>y>>c;
g[x].push_back(make_pair(y, c));
}

dijkstra(1);

for(i=2; i<=n; i++)
    if(d[i]!=1000000) fout<<d[i]<<' ';
else fout<<0<<' ';



    return 0;
}