#include<iostream>
#include<fstream>
#include<vector>
#include<set>
#include<cstring>
#include<utility>
#define NMAX 50001
#define f first
#define s second
#define inf 1000000
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n,m;
vector<pair<int,int> >g[NMAX];
set<pair<int,int> >st;
int dmin[NMAX];
struct cmpv
{
public :
    bool operator () (const int &x,const int & y)
    {
        return dmin[x]<dmin[y];
    }
};
void read()
{
    fin>>n>>m;
    int x,y,c;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        g[x].push_back(make_pair(y,c));
        g[y].push_back(make_pair(x,c));
    }
    fin.close();
}
void dijsktra(int x)
{
   memset(dmin,inf,sizeof(dmin));
   dmin[x]=0;

   st.insert(make_pair(0,x));
   while(!st.empty())
   {
       x=st.begin()->s;
       st.erase(st.begin());
       for(int i=0;i<g[x].size();++i)
       {
           if(dmin[g[x][i].f]>dmin[x]+g[x][i].s)
           {
               dmin[g[x][i].f]=dmin[x]+g[x][i].s;
               st.insert(make_pair(dmin[g[x][i].f],g[x][i].f));
           }
       }
   }
for(int i=1;i<=n;i++)
    fout<<dmin[i]<<" ";
}
int main()
{
    read();
    dijsktra(1);
    fout.close();
    return 0;
}