#include<fstream>
#include<queue>
#include<list>
#include<bitset>

using namespace std;

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");


list<pair<int, int>> adj[50001];
priority_queue<pair<int, int>> Q;
int dist[50001];
bitset<50001> vis;


void readGraph(const int& m)
{
  int master, slave, time;

  for(int i=0; i<m; i++)
  {
    cin>>master>>slave>>time;
    adj[master].push_back({time, slave});
  }
}

void addQ(int node, int distance)
{  
  if(!adj[node].empty())
  {
    //cout<<"\n";
    for(auto p: adj[node])
    {
      if(vis[p.second]==0)
      {
        int n = p.second, d=p.first;
        //cout<<n<<" ";
        Q.push({-1*(distance+d), n});   
      }
    }
    //cout<<"\n";
  }
}

void Dijkstra()
{
  Q.push({0, 1});

  while(!Q.empty())
  {
    int node=Q.top().second, distance=-1*(Q.top().first); 
    //cout<<node<<" "<<vis[node]<<" ";    
    Q.pop();

    if(vis[node]==0)
    {
      //cout<<node<<" ";
      vis[node]=1;
      dist[node]=distance;
      addQ(node, distance);
    }
  }
  //cout<<"\n";
}

void writeDist(const int& n)
{
  for(int i=2; i<=n; i++)
  {
    cout<<dist[i]<<" ";
  }
}


int main()
{
  ios::sync_with_stdio(false);

  int n,m;
  cin>>n>>m;

  readGraph(m);
  Dijkstra();
  
  writeDist(n);

  return 0;
}